Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)

DOI10.1007/s00037-022-00231-8OpenAlexW3102910963MaRDI QIDQ2087770

Jamie Sikora, Miklos Santha, Justin Yirka, Aarthi Sundaram, Sevag Gharibian

Publication date: 21 October 2022

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-022-00231-8

zbMATH Keywords

semidefinite programmingquantum computingpolynomial hierarchycomplexity theoryQMA(2)Toda's theorem

Mathematics Subject Classification ID

Semidefinite programming (90C22) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Quantum Arthur-Merlin games
• NP is as easy as detecting unique solutions
• Complete sets and the polynomial-time hierarchy
• Geometric algorithms and combinatorial optimization.
• An oracle builder's toolkit
• Complexity limitations on quantum computation
• A note on the circuit complexity of PP
• QMA with Subset State Witnesses
• Hardness of Approximation for Quantum Problems
• Zero-knowledge against quantum attacks
• Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
• A Full Characterization of Quantum Advice
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• PP is as Hard as the Polynomial-Time Hierarchy
• Algebraic methods for interactive proof systems
• Complexity classes defined by counting quantifiers
• Revisiting the simulation of quantum Turing machines by quantum circuits
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)