Copertina

Lower bounds for quantum-inspired classical algorithms via communication complexity

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Mande, Nikhil S., Shao, Changpeng
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Quantum Physics Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

Tight Bounds for Quantum Phase Estimation and Related Problems
di: Mande, Nikhil S., et al.
Pubblicazione: (2023)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
di: Cornelissen, Arjan, et al.
Pubblicazione: (2022)

Quantum Search With Generalized Wildcards
di: Cornelissen, Arjan, et al.
Pubblicazione: (2025)

Low-degree approximation of QAC$^0$ circuits
di: Montanaro, Ashley, et al.
Pubblicazione: (2024)

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

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

Instance complexity of Boolean functions
di: Liu, Alison Hsiang-Hsuan, et al.
Pubblicazione: (2023)

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
di: Ji, Zhengfeng, et al.
Pubblicazione: (2026)

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
di: Krovi, Hari
Pubblicazione: (2024)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
di: Miloschewsky, David, et al.
Pubblicazione: (2024)

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

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

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

A full dichotomy for Holant$^c$, inspired by quantum computation
di: Backens, Miriam
Pubblicazione: (2022)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
di: Anand, Kartik, et al.
Pubblicazione: (2025)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
di: Mehraban, Saeed, et al.
Pubblicazione: (2023)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
di: Gall, François Le, et al.
Pubblicazione: (2023)

Quantum Sabotage Complexity
di: Cornelissen, Arjan, et al.
Pubblicazione: (2024)

Distributed inner product estimation with limited quantum communication
di: Arunachalam, Srinivasan, et al.
Pubblicazione: (2024)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
di: Panova, Greta
Pubblicazione: (2025)

Query Complexity with Unknowns
di: Mande, Nikhil S., et al.
Pubblicazione: (2024)

A note on quantum lower bounds for local search via congestion and expansion
di: Brânzei, Simina, et al.
Pubblicazione: (2024)

A polynomial-time classical algorithm for noisy quantum circuits
di: Schuster, Thomas, et al.
Pubblicazione: (2024)

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

Improved separation between quantum and classical computers for sampling and functional tasks
di: Marshall, Simon C., et al.
Pubblicazione: (2024)

Classical simulability of quantum circuits followed by sparse classical post-processing
di: Takahashi, Yasuhiro, et al.
Pubblicazione: (2026)

Space-bounded quantum interactive proof systems
di: Gall, François Le, et al.
Pubblicazione: (2024)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
di: Schreiber, Franz J., et al.
Pubblicazione: (2025)

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

Computational hardness of estimating quantum entropies via binary entropy bounds
di: Liu, Yupan
Pubblicazione: (2026)

Clifford testing: algorithms and lower bounds
di: Hinsche, Marcel, et al.
Pubblicazione: (2025)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
di: Daskin, Ammar
Pubblicazione: (2024)

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

How hard is it to verify a classical shadow?
di: Karaiskos, Georgios, et al.
Pubblicazione: (2025)

Improved Lower Bounds for QAC0
di: Joshi, Malvika Raj, et al.
Pubblicazione: (2025)

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

Pseudorandom quantum authentication
di: Haug, Tobias, et al.
Pubblicazione: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
di: Grewal, Sabee, et al.
Pubblicazione: (2024)