Fetching the paper…
Reading the bibliography…
We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighbor gates in 3D even when its implementation is corrupted by noise.
Σ 1 1 \Sigma^{1}_{1} -Formulae on finite structures
Miklós Ajtai · 1983
Earlier work this paper cites.
Parity, circuits, and the polynomial-time hierarchy
Merrick Furst, James B. Saxe, and Michael Sipser · 1984
Earlier work this paper cites.
Separating the Polynomial-time Hierarchy by Oracles
Andrew Chi-Chih Yao · 1985
Earlier work this paper cites.
Almost Optimal Lower Bounds for Small Depth Circuits
Johan Håstad · 1986
Earlier work this paper cites.
Computational limitations for small-depth circuits
Johan Håstad · 1987
Earlier work this paper cites.
Extreme quantum entanglement in a superposition of macroscopically distinct states
David Mermin · 1990
Earlier work this paper cites.
Incompatible results of quantum measurements
Asher Peres · 1990
Earlier work this paper cites.
A switching lemma primer
Paul Beame · 1994
Earlier work this paper cites.
Good quantum error-correcting codes exist
A Robert Calderbank and Peter W Shor · 1996
Earlier work this paper cites.
Multiple-particle interference and quantum error correction
Andrew Steane · 1996
Earlier work this paper cites.
Fault-tolerant quantum computation with constant error
Dorit Aharonov and Michael Ben-Or · 1997
Earlier work this paper cites.
Quantum codes on a lattice with boundary, 1998
Sergey B. Bravyi and Alexei Yu. Kitaev · 1998
Cited alongside, same era.
Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations
Daniel Gottesman and Isaac L. Chuang · 1999
Cited alongside, same era.
Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
Barbara M. Terhal and David P. DiVincenzo · 2004
Cited alongside, same era.
Quantum fan-out is powerful
Peter Høyer and Robert Špalek · 2005
Cited alongside, same era.
Long-range quantum entanglement in noisy cluster states
Robert Raussendorf, Sergey Bravyi, and Jim Harrington · 2005
Cited alongside, same era.
Proof of finite surface code threshold for matching
Austin G Fowler · 2012
Cited alongside, same era.
Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, and Robert König · 2018
Later among the works it cites.
Constant overhead quantum fault-tolerance with quantum expander codes
Omar Fawzi, Antoine Grospellier, and Anthony Leverrier · 2018
Later among the works it cites.
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal · 2019
Later among the works it cites.
Average-Case Quantum Advantage with Shallow Circuits
François Le Gall · 2019
Later among the works it cites.
Quantum advantage with noisy shallow circuits
Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel · 2020
Later among the works it cites.
Interactive shallow Clifford circuits: Quantum advantage against NC 1 and beyond
Daniel Grier and Luke Schaeffer · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Fault-tolerant quantum computation with constant overhead
Daniel Gottesman · 2014
Cited alongside, same era.
Single-shot fault-tolerant quantum error correction
Héctor Bombín · 2015
Cited alongside, same era.
Transversal clifford gates on folded surface codes
Jonathan E. Moussa · 2016
Cited alongside, same era.
An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC0
Benjamin Rossman · 2017
Cited alongside, same era.
Later among the works it cites.
Interactive quantum advantage with noisy, shallow clifford circuits, 2021
Daniel Grier, Nathan Ju, and Luke Schaeffer · 2021
Later among the works it cites.
Quantum Advantage with Shallow Circuits Under Arbitrary Corruption
Atsuya Hasegawa and François Le Gall · 2021
Later among the works it cites.
Single-qubit gate teleportation provides a quantum advantage, 2022
Libor Caha, Xavier Coiteux-Roy, and Robert Koenig · 2022
Later among the works it cites.
Possibilistic simulation of quantum circuits by classical circuits
Daochen Wang · 2022
Later among the works it cites.