Fetching the paper…
Reading the bibliography…
Recently Brakerski, Christiano, Mahadev, Vazirani and Vidick (FOCS 2018) have shown how to construct a test of quantumness based on the learning with errors (LWE) assumption: a test that can be solved efficiently by a quantum computer but cannot be solved by a classical polynomial-time computer under the LWE assumption.
Depth efficient neural networks for division and related problems
Kai-Yeung Siu, Jehoshua Bruck, Thomas Kailath, and Thomas Hofmeister · 1993
Earlier work this paper cites.
Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations
Daniel Gottesman and Isaac L. Chuang · 1999
Earlier work this paper cites.
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang · 2000
Earlier work this paper cites.
Creating superpositions that correspond to efficiently integrable probability distributions
Lov Grover and Terry Rudolph · 2002
Earlier work this paper cites.
Quantum computation by measurement and quantum memory
Michael A. Nielsen · 2003
Earlier work this paper cites.
Quantum computation by measurements
Debbie W. Leung · 2004
Earlier work this paper cites.
Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
Barbara M. Terhal and David P. DiVincenzo · 2004
Earlier work this paper cites.
Quantum fan-out is powerful
Peter Høyer and Robert Spalek · 2005
Earlier work this paper cites.
An introduction to measurement based quantum computation
Richard Jozsa · 2005
Earlier work this paper cites.
Parallelizing quantum circuits
Anne Broadbent and Elham Kashefi · 2008
Earlier work this paper cites.
On lattices, learning with errors, random linear codes, and cryptography
Oded Regev · 2009
Earlier work this paper cites.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd · 2010
Earlier work this paper cites.
Computational depth complexity of measurement-based quantum computation
Dan E. Browne, Elham Kashefi, and Simon Perdrix · 2010
Earlier work this paper cites.
The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov · 2011
Cited alongside, same era.
Trapdoors for lattices: Simpler, tighter, faster, smaller
Daniele Micciancio and Chris Peikert · 2012
Cited alongside, same era.
BosonSampling is far from uniform
Scott Aaronson and Alex Arkhipov · 2014
Cited alongside, same era.
Hardness of classically simulating the one-clean-qubit model
Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons · 2014
Cited alongside, same era.
Average-case complexity versus approximate simulation of commuting quantum computations
Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd · 2016
Cited alongside, same era.
Quantum supremacy through the quantum approximate optimization algorithm
Edward Farhi and Aram W. Harrow · 2016
Classical verification of quantum computations
Urmila Mahadev · 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.
“Quantum supremacy” and the complexity of random circuit sampling
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, and Umesh Vazirani · 2019
Later among the works it cites.
Quantum advantage with noisy shallow circuits in 3d
Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel · 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.
Simpler proofs of quantumness
Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, and Thomas Vidick · 2020
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Computational quantum-classical boundary of noisy commuting quantum circuits
Keisuke Fujii and Shuhei Tamate · 2016
Cited alongside, same era.
Collapse of the hierarchy of constant-depth exact quantum circuits
Yasuhiro Takahashi and Seiichiro Tani · 2016
Cited alongside, same era.
Complexity-theoretic foundations of quantum supremacy experiments
Scott Aaronson and Lijie Chen · 2017
Cited alongside, same era.
Achieving quantum supremacy with sparse and noisy commuting quantum circuits
Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd · 2017
Cited alongside, same era.
A cryptographic test of quantumness and certifiable randomness from a single quantum device
Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh V. Vazirani, and Thomas Vidick · 2018
Cited alongside, same era.
Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, and Robert König · 2018
Cited alongside, same era.
Later among the works it cites.
Quantum garbled circuits
Zvika Brakerski and Henry Yuen · 2020
Later among the works it cites.
Interactive shallow Clifford circuits: quantum advantage against NC 1 and beyond
Daniel Grier and Luke Schaeffer · 2020
Later among the works it cites.
Device-independent quantum key distribution from computational assumptions
Tony Metger, Yfke Dulek, Andrea Coladangelo, and Rotem Arnon-Friedman · 2020
Later among the works it cites.
Trading locality for time: Certifiable randomness from low-depth circuits
Matthew Coudron, Jalex Stark, and Thomas Vidick · 2021
Closest in time.
Classically-verifiable quantum advantage from a computational Bell test
Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, and Norman Y. Yao · 2021
Closest in time.
Self-testing of a single quantum device under computational assumptions
Tony Metger and Thomas Vidick · 2021
Closest in time.