A conditional-fidelity witness on projected small subsystems certifies entanglement, magic, and circuit complexity of generic many-body states with constant sample complexity, with fidelity certification supported by numerics.
Black Holes and Complexity Classes
2 Pith papers cite this work, alongside 12 external citations. Polarity classification is still indexing.
2
Pith papers citing it
12
external citations · Pith
abstract
It is not known what the limitations are on using quantum computation to speed up classical computation. An example would be the power to speed up PSPACE-complete computations. It is also not known what the limitations are on the duration of time over which classical general relativity can describe the interior geometry of black holes. What is known is that these two questions are closely connected: the longer GR can describe black holes, the more limited are quantum computers. This conclusion, formulated as a theorem, is a result of unpublished work done by Scott Aaronson and myself which I explain here.
citation-role summary
background 1
citation-polarity summary
fields
quant-ph 2roles
background 1polarities
background 1representative citing papers
In finite-depth random linear optical circuits, entanglement grows at most diffusively and robust circuit complexity scales similarly, with depth bounds ensuring near-maximal subsystem entanglement and closeness to Haar unitaries.
citing papers explorer
-
Certifying localizable quantum properties with constant sample complexity
A conditional-fidelity witness on projected small subsystems certifies entanglement, magic, and circuit complexity of generic many-body states with constant sample complexity, with fidelity certification supported by numerics.
-
Entanglement and circuit complexity in finite-depth random linear optical networks
In finite-depth random linear optical circuits, entanglement grows at most diffusively and robust circuit complexity scales similarly, with depth bounds ensuring near-maximal subsystem entanglement and closeness to Haar unitaries.