Fetching the paper…
Reading the bibliography…
A general quantum circuit can be simulated classically in exponential time.
“Nested dissection of a regular finite element mesh”
Alan George · 1973
Earlier work this paper cites.
“Generalized nested dissection”
Richard J Lipton, Donald J Rose, and Robert Endre Tarjan · 1979
Earlier work this paper cites.
“A separator theorem for planar graphs”
Richard J. Lipton and Robert Endre Tarjan · 1979
Earlier work this paper cites.
“A generalization of the fast LUP matrix decomposition algorithm and applications”
Oscar H Ibarra, Shlomo Moran, and Roger Hui · 1982
Earlier work this paper cites.
“Complexity of finding embeddings in a k k -tree”
Stefan Arnborg, Derek G Corneil, and Andrzej Proskurowski · 1987
Earlier work this paper cites.
“Problems complete for ⊕ L \oplus\textsf{L} ”
Carsten Damm · 1990
Earlier work this paper cites.
“Better algorithms for the pathwidth and treewidth of graphs”
Hans L Bodlaender and Ton Kloks · 1991
Earlier work this paper cites.
“A tourist guide through treewidth”
HL Bodlaender · 1993
Earlier work this paper cites.
“Planar separators and parallel polygon triangulation”
Michael T Goodrich · 1995
Earlier work this paper cites.
“The Heisenberg representation of quantum computers” (1998)
Daniel Gottesman · 1998
Earlier work this paper cites.
“A one-way quantum computer”
Robert Raussendorf and Hans J Briegel · 2001
Earlier work this paper cites.
“Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games” (2002)
Barbara M Terhal and David P DiVincenzo · 2002
Earlier work this paper cites.
“Generalized inverses: theory and applications”
Adi Ben-Israel and Thomas NE Greville · 2003
Earlier work this paper cites.
“Clifford group, stabilizer states, and linear and quadratic operations over GF \mathrm{GF} (2)”
Jeroen Dehaene and Bart De Moor · 2003
Earlier work this paper cites.
“Improved simulation of stabilizer circuits”
Scott Aaronson and Daniel Gottesman · 2004
Earlier work this paper cites.
“Graphical description of the action of local Clifford transformations on graph states”
Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor · 2004
Earlier work this paper cites.
“Fast simulation of stabilizer circuits using a graph-state representation”
Simon Anders and Hans J Briegel · 2006
Cited alongside, same era.
“Simulating quantum computation by contracting tensor networks”
Igor L Markov and Yaoyun Shi · 2008
Cited alongside, same era.
“Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond” (2008)
M Van den Nest · 2008
Cited alongside, same era.
“Solving linear systems through nested dissection”
Noga Alon and Raphael Yuster · 2010
Cited alongside, same era.
“Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy”
Michael J Bremner, Richard Jozsa, and Dan J Shepherd · 2011
Cited alongside, same era.
“The computational complexity of linear optics”
Scott Aaronson and Alex Arkhipov · 2011
Personal communication, 2017 (2017)
Sergey Bravyi · 2017
Later among the works it cites.
“Quantum advantage with shallow circuits”
Sergey Bravyi, David Gosset, and Robert König · 2018
Later among the works it cites.
“Classical simulation of intermediate-size quantum circuits” (2018)
Jianxin Chen, Fang Zhang, Cupjin Huang, Michael Newman, and Yaoyun Shi · 2018
Later among the works it cites.
“Quantum supremacy using a programmable superconducting processor”
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al · 2019
Later among the works it cites.
“Simulation of quantum circuits by low-rank stabilizer decompositions”
Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard · 2019
Later among the works it cites.
“Leveraging secondary storage to simulate deep 54-qubit Sycamore circuits” (2019)
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
“Realization of three-qubit quantum error correction with superconducting circuits”
Matthew D Reed, Leonardo DiCarlo, Simon E Nigg, Luyan Sun, Luigi Frunzio, Steven M Girvin, and Robert J Schoelkopf · 2012
Cited alongside, same era.
“Demonstration of a quantum error detection code using a square lattice of four superconducting qubits”
Antonio D Córcoles, Easwar Magesan, Srikanth J Srinivasan, Andrew W Cross, Matthias Steffen, Jay M Gambetta, and Jerry M Chow · 2015
Cited alongside, same era.
“Extending the lifetime of a quantum bit with error correction in superconducting circuits”
Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, et al · 2016
Cited alongside, same era.
“Improved classical simulation of quantum circuits dominated by Clifford gates”
Sergey Bravyi and David Gosset · 2016
Cited alongside, same era.
“A c k n c^{k}n 5-approximation algorithm for treewidth”
Hans L. Bodlaender, Pål Grøonås Drange, Markus S. Dregi, Fedor V. Fomin, Daniel Lokshtanov, and Michał Pilipczuk · 2016
Cited alongside, same era.
“Trading classical and quantum computational resources”
Sergey Bravyi, Graeme Smith, and John A Smolin · 2016
Cited alongside, same era.
Edwin Pednault, John A Gunnels, Giacomo Nannicini, Lior Horesh, and Robert Wisnieff · 2019
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.
“Stabilizer circuits, quadratic forms, and computing matrix rank” (2019)
Chaowen Guan and Kenneth W Regan · 2019
Later among the works it cites.
“Spoofing linear cross-entropy benchmarking in shallow quantum circuits” (2020)
Boaz Barak, Chi-Ning Chou, and Xun Gao · 2020
Closest in time.
“Interactive shallow Clifford circuits: quantum advantage against 𝖭𝖢 1 \mathsf{NC}^{1} and beyond”
Daniel Grier and Luke Schaeffer · 2020
Closest in time.
“Quantum advantage with noisy shallow circuits”
Sergey Bravyi, David Gosset, Robert Koenig, and Marco Tomamichel · 2020
Closest in time.
“A refined laser method and faster matrix multiplication” (2020)
Josh Alman and Virginia Vassilevska Williams · 2020
Closest in time.
“Establishing the quantum supremacy frontier with a 281 pflop/s simulation”
Benjamin Villalonga, Dmitry Lyakh, Sergio Boixo, Hartmut Neven, Travis S Humble, Rupak Biswas, Eleanor G Rieffel, Alan Ho, and Salvatore Mandrà · 2020
Closest in time.
commons.wikimedia.org/wiki/File:Tree_decomposition.svg , accessed 08/31/2020
David Eppstein (2007) · 2020
Closest in time.
“Clifford simulation: Techniques and applications”
Alex Kerzner · 2021
Closest in time.