Average-case quantum advantage with shallow circuits
From MaRDI portal
Publication:5091772
Recommendations
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
- Quantum advantage through the magic pentagram problem
- Quantum advantage with shallow circuits
- On the need for large Quantum depth
Cites work
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Collapse of the hierarchy of constant-depth exact quantum circuits
- Complexity-theoretic foundations of quantum supremacy experiments
- Counting, fanout and the complexity of quantum ACC
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- Multiparty entanglement in graph states
- Oracle separation of BQP and PH
- Quantum advantage for the LOCAL model in distributed computing
- Quantum advantage with shallow circuits
- Quantum Complexity Theory
- Quantum computation and quantum information. 10th anniversary edition
- Quantum fan-out is powerful
- Quantum Supremacy and the Complexity of Random Circuit Sampling
- The computational complexity of linear optics
- Trading locality for time: certifiable randomness from low-depth circuits
- Understanding quantum algorithms via query complexity
Cited in
(5)- Power of uninitialized qubits in shallow quantum circuits
- scientific article; zbMATH DE number 7087310 (Why is no real title available?)
- An Exact and Practical Classical Strategy for 2D Graph State Sampling
- Parity vs. \(\text{AC}^0\) with simple quantum preprocessing
- Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract)
This page was built for publication: Average-case quantum advantage with shallow circuits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091772)
