Copertina

Direct sum theorems beyond query complexity

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Suruga, Daiki
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Quantum Physics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Another generalization of Hadamard test: Optimal sample complexities for learning functions on the unitary group
di: Suruga, Daiki
Pubblicazione: (2025)

Separations in query complexity for total search problems
di: Ben-David, Shalev, et al.
Pubblicazione: (2024)

On query complexity measures and their relations for symmetric functions
di: Mittal, Rajat, et al.
Pubblicazione: (2021)

Quantum and classical query complexities of functions of matrices
di: Montanaro, Ashley, et al.
Pubblicazione: (2023)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
di: Yao, Penghui, et al.
Pubblicazione: (2023)

Classical versus quantum queries in quantum PCPs with classical proofs
di: Buhrman, Harry, et al.
Pubblicazione: (2024)

Learning unitaries with quantum statistical queries
di: Angrisani, Armando
Pubblicazione: (2023)

Conjugate queries can help
di: Tang, Ewin, et al.
Pubblicazione: (2025)

Magic and communication complexity
di: Girish, Uma, et al.
Pubblicazione: (2025)

Quasi-quantum states and the quasi-quantum PCP theorem
di: Arad, Itai, et al.
Pubblicazione: (2024)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
di: Apers, Simon, et al.
Pubblicazione: (2021)

Quantum computational complexity of matrix functions
di: Cifuentes, Santiago, et al.
Pubblicazione: (2024)

Computational complexity of isometric tensor network states
di: Malz, Daniel, et al.
Pubblicazione: (2024)

Physical complexity and black hole quantum computers
di: Reilly, Michele, et al.
Pubblicazione: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
di: Anshu, Anurag, et al.
Pubblicazione: (2024)

On the communication complexity of finding a king in a tournament
di: Mande, Nikhil S., et al.
Pubblicazione: (2024)

On the complexity of estimating ground state entanglement and free energy
di: Gharibian, Sevag, et al.
Pubblicazione: (2025)

Unambiguous parity-query complexity
di: Gavinsky, Dmytro
Pubblicazione: (2024)

On classical advice, sampling advice and complexity assumptions for learning separations
di: Pérez-Guijarro, Jordi
Pubblicazione: (2024)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
di: Rayudu, Chaithanya
Pubblicazione: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
di: Mande, Nikhil S., et al.
Pubblicazione: (2024)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
di: Sakamoto, Kazuki, et al.
Pubblicazione: (2025)

Quantum complexity of the Kronecker coefficients
di: Bravyi, Sergey, et al.
Pubblicazione: (2023)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
di: Rudolph, Dorian, et al.
Pubblicazione: (2024)

Random regular graph states are complex at almost any depth
di: Ghosh, Soumik, et al.
Pubblicazione: (2024)

An efficient quantum parallel repetition theorem and applications
di: Bostanci, John, et al.
Pubblicazione: (2023)

Quantum state testing beyond the polarizing regime and quantum triangular discrimination
di: Liu, Yupan
Pubblicazione: (2023)

Between the deterministic and non-deterministic query complexity
di: Gerbner, Dániel
Pubblicazione: (2019)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
di: Lemus, Mariano, et al.
Pubblicazione: (2023)

A complexity phase transition at the EPR Hamiltonian
di: Marwaha, Kunal, et al.
Pubblicazione: (2026)

Learning quantum states and unitaries of bounded gate complexity
di: Zhao, Haimeng, et al.
Pubblicazione: (2023)

On the average-case complexity of learning output distributions of quantum circuits
di: Nietner, Alexander, et al.
Pubblicazione: (2023)

Computational complexity of the homology problem with orientable filtration: MA-completeness
di: Hayakawa, Ryu, et al.
Pubblicazione: (2025)

Towards a complexity-theoretic dichotomy for TQFT invariants
di: Bridges, Nicolas, et al.
Pubblicazione: (2025)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
di: Dinur, Irit, et al.
Pubblicazione: (2024)

The Complexity of Translationally Invariant Problems beyond Ground State Energies
di: Watson, James D., et al.
Pubblicazione: (2020)

Average-case deterministic query complexity of boolean functions with fixed weight
di: Li, Yuan, et al.
Pubblicazione: (2024)

Computational complexity of Berry phase estimation in topological phases of matter
di: Hayakawa, Ryu, et al.
Pubblicazione: (2025)

A learning theory for quantum photonic processors and beyond
di: Rosati, Matteo
Pubblicazione: (2022)

Directed st-connectivity with few paths is in quantum logspace
di: Apers, Simon, et al.
Pubblicazione: (2024)