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
8 Pith papers cite this work. Polarity classification is still indexing.
8
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 1
citation-polarity summary
roles
background 1polarities
background 1representative 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.
citing papers explorer
-
A Relativizing MIP for BQP
BQP is contained in MIP relative to every classical oracle via a new PCP construction for BQP^O inspired by Grover-Rudolph state synthesis.
-
Certifying localizable quantum properties with constant sample complexity
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.
-
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.
-
Quantum Finite Temperature Lanczos Method
QFTLM computes thermal expectation values on quantum computers by merging quantum Krylov methods with efficient typical-state preparation for trace estimation.
-
Quantum Circuit Overhead
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.
-
Stringy Effects on Holographic Complexity: The Complete Volume in Dynamical Spacetimes
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 Multi-Level Integrity Evaluation Framework for Quantum Circuits under Controlled Anomaly Injection
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.
-
From Fundamental Dynamics to Applied Cryptography: Studies on the Quantum Speed Limit and Fully Passive Quantum Key Distribution
Thesis exploring quantum speed limits on dynamical evolution alongside a fully passive quantum key distribution scheme.