A note on quantum lower bounds for local search via congestion and expansion

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Brânzei, Simina, Recker, Nicholas J.
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Lower Bounds for Local Search
by: Brânzei, Simina, et al.
Published: (2024)

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube
by: Brânzei, Simina, et al.
Published: (2024)

Tarski Lower Bounds from Multi-Dimensional Herringbones
by: Brânzei, Simina, et al.
Published: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
by: Brânzei, Simina, et al.
Published: (2020)

The Query Complexity of Local Search in Rounds on General Graphs
by: Brânzei, Simina, et al.
Published: (2026)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

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

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

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

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

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

Quantum search by continuous-time quantum walk on t-designs
by: Lugão, Pedro H. G., et al.
Published: (2023)

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

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)

QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
by: Chen, Yanlin, et al.
Published: (2023)

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

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

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

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

A slightly improved upper bound for quantum statistical zero-knowledge
by: Gall, François Le, et al.
Published: (2025)

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

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

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

Complexity of quantum circuits via sensitivity, magic, and coherence
by: Bu, Kaifeng, et al.
Published: (2022)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

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

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

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

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

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

Bell sampling from quantum circuits
by: Hangleiter, Dominik, et al.
Published: (2023)

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

A simplified version of the quantum OTOC$^{(2)}$ problem
by: King, Robbie, et al.
Published: (2025)

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

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

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