REVIEW 16 cited by
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original 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.
Forward citations
Cited by 16 Pith papers
-
Online Shadow Tomography Matching the Classical Bounds
Online shadow tomography can be solved with O(log m sqrt(log d)/eps^3) or O(sqrt(m)/eps^2) copies, matching known classical rates, but the first bound's key proof lemma contains an invalid inequality.
-
Explicit Separations for One-Query Unitary Synthesis
One-query lower bounds for permutation and alternating-basis phase unitaries, plus a constant-approximation one-query algorithm for complex phase unitaries.
-
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.
-
Quantum Simultaneous Protocols without Public Coins using Modified Equality Queries
A compiler converts classical modified-equality-query decision trees into quantum simultaneous protocols with only O(k log D log n) qubits, proving that quantum messages can replace public coins for several multi-part...
-
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.
-
Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates
Explicit n imes n matrices over Z_2 require 4n−o(n) CNOT/row/2-local linear gates, and the same bound holds for the quantum complexity of the associated affine permutations.
-
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.
-
Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
The paper's claimed collapses of quantum-classical PCPs and the quantum polynomial hierarchy rest on invalid reductions, so the main theorems are unsupported.
-
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.
-
Holographic complexity of charged Taub-NUT-AdS black holes
For charged Taub-NUT-AdS black holes, the late-time holographic complexity growth rate includes Misner string thermodynamic terms and the total electric charge, and adding a Maxwell boundary term with gamma=1/2 restor...
-
Position: Quantum Program Generation Must Prioritize Validity Over Probabilistic Scaling
The paper argues that probabilistic scaling alone cannot fix the validity gap in quantum circuit generation, so quantum code assistants must build verification into generation rather than filter outputs after the fact.
-
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.
-
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.
-
Physical complexity and black hole quantum computers
Free energy unifies physical time and space complexity, and error-correction scaling makes black hole quantum computers physically intractable.
-
Emergent Holographic Spacetime from Quantum Information
Takayanagi's essay outlines a research program in which holographic spacetime, including the time direction, may emerge from entanglement, complexity, and complex-valued pseudo-entropy, without presenting a new derivation.
-
Rethinking quantum information in gravity and fields
The paper organizes important open questions in quantum gravity and quantum information into four themes without presenting new results or derivations.
Discussion (0). Continue with ORCID to comment.