BQP is contained in MIP relative to every classical oracle via a new PCP construction for BQP^O inspired by Grover-Rudolph state synthesis.
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
9 Pith papers cite this work. Polarity classification is still indexing.
9
Pith papers citing it
abstract
These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21-25, 2016. The focus is quantum circuit complexity---i.e., the minimum number of gates needed to prepare a given quantum state or apply a given unitary transformation---as a unifying theme tying together several topics of recent interest in the field. Those topics include the power of quantum proofs and advice states; how to construct quantum money schemes secure against counterfeiting; and the role of complexity in the black-hole information paradox and the AdS/CFT correspondence (through connections made by Harlow-Hayden, Susskind, and others). The course was taught to a mixed audience of theoretical computer scientists and quantum gravity / string theorists, and starts out with a crash course on quantum information and computation in general.
citation-role summary
background 3
citation-polarity summary
roles
background 3polarities
background 3representative citing papers
A new framework certifies global quantum properties including multipartite entanglement, circuit complexity, and quantum magic on small subsystems with constant sample complexity via local Pauli measurements.
Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.
QFTLM computes thermal expectation values on quantum computers by merging quantum Krylov methods with efficient typical-state preparation for trace estimation.
Introduces QCO and T-QCO measures and numerically shows that the T gate is non-optimal for completing the Clifford set among order-8 gates.
Gauss-Bonnet corrections to the complete volume proposal introduce a competition effect in static black holes while preserving momentum-governed growth rates and logarithmic scrambling times in dynamical Vaidya geometries.
A three-metric framework (SIS, OIS, IGS) detects anomalies in quantum circuits more reliably than structural checks alone, as shown by controlled injections where high structural similarity still misses most behavioral deviations.
Thesis exploring quantum speed limits on dynamical evolution alongside a fully passive quantum key distribution scheme.
The paper organizes important open questions in quantum gravity and quantum information into four themes without presenting new results or derivations.
citing papers explorer
-
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
Any n-qubit unitary can be implemented approximately with Õ(2^{n/2}) oracle queries or exactly with Õ(2^{n/2}) circuit depth via Grover search reductions, with matching lower bounds for certain implementations.