Cover Image

A sharp interaction-degree threshold for simulating QAOA

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Āboliņš, Ralfs, Ambainis, Andris
Format:	Preprint
Published:	2026
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quantum Advantages in (n,d)->1 Random Access Codes
by: Ambainis, Andris, et al.
Published: (2015)

A Hierarchy for Constant Communication Complexity
by: Ambainis, Andris, et al.
Published: (2025)

Quantum Algorithm for Apprenticeship Learning
by: Ambainis, Andris, et al.
Published: (2025)

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

Rational degree is polynomially related to degree
by: Kothari, Robin, et al.
Published: (2026)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

Fast simulation of planar Clifford circuits
by: Gosset, David, et al.
Published: (2020)

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

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

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

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

Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
by: Barthe, Alice, et al.
Published: (2024)

Low degree conjecture implies sharp computational thresholds in stochastic block model
by: Ding, Jingqiu, 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)

Fundamental Limitations of QAOA on Constrained Problems and a Route to Exponential Enhancement
by: Onah, Chinonso, et al.
Published: (2025)

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

Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation
by: Martinez, Victor, et al.
Published: (2025)

A Critical Comment on 'Entropy Computing: A Paradigm for Optimization in Open Photonic Systems'
by: Moosavian, Ali Hamed, et al.
Published: (2026)

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

A Quantum Unique Games Conjecture
by: Mousavi, Hamoon, et al.
Published: (2024)

A Cautionary Note on Quantum Oracles
by: Agarwal, Avantika, et al.
Published: (2025)

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

A Criterion for Post-Selected Quantum Advantage
by: Karamchedu, Chaitanya, et al.
Published: (2024)

A Note on the Complexity of the Spectral Gap Problem
by: Yirka, Justin
Published: (2025)

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

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

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

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)

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

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
by: Guseynov, Nikita, et al.
Published: (2026)

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

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
by: Grillo, Sebastian Alberto, et al.
Published: (2026)

A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream
by: Kordonowy, Steven, et al.
Published: (2026)

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

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
by: Grier, Daniel, et al.
Published: (2026)

Quantum state isomorphism problems for groups
by: Gheorghiu, Alexandru, et al.
Published: (2026)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
by: Miloschewsky, David, et al.
Published: (2026)