Fetching the paper…
Reading the bibliography…
Certified randomness has a long history in quantum information, with many potential applications.
R. Movassagh · 1909
Earlier work this paper cites.
On a formula for the product-moment coefficient of any order of a normal frequency distribution in any number of variables
L. Isserlis · 1918
Earlier work this paper cites.
Fluctuations of nuclear reaction widths
C. E. Porter and R. G. Thomas · 1956
Earlier work this paper cites.
Computational limitations for small depth circuits
J. Håstad · 1986
Earlier work this paper cites.
Does co-NP have short interactive proofs?
R. B. Boppana, J. Håstad, and S. Zachos · 1987
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. H. Bennett, E. Bernstein, G. Brassard, and U. V. Vazirani · 1997
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. V. Vazirani · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1997
Earlier work this paper cites.
Adaptive estimation of a quadratic functional by model selection
B. Laurent and P. Massart · 2000
Earlier work this paper cites.
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
B. M. Terhal and D. P. DiVincenzo · 2004
Earlier work this paper cites.
On approximate majority and probabilistic time
E. Viola · 2007
Earlier work this paper cites.
Unbalanced expanders and randomness extractors from parvaresh-vardy codes
V. Guruswami, C. Umans, and S. P. Vadhan · 2009
Earlier work this paper cites.
BQP and the polynomial hierarchy
S. Aaronson · 2010
Earlier work this paper cites.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
M. J. Bremner, R. Jozsa, and D. J. Shepherd · 2010
Earlier work this paper cites.
Random numbers certified by bell’s theorem
S. Pironio, A. Acín, S. Massar, et al · 2010
Earlier work this paper cites.
Probabilistic search algorithms with unique answers and their cryptographic applications
E. Gat and S. Goldwasser · 2011
Earlier work this paper cites.
The computational complexity of linear optics
S. Aaronson and A. Arkhipov · 2013
Earlier work this paper cites.
On beating the hybrid argument
B. Fefferman, R. Shaltiel, C. Umans, and E. Viola · 2013
Earlier work this paper cites.
On the possibilities and limitations of pseudodeterministic algorithms
O. Goldreich, S. Goldwasser, and D. Ron · 2013
Earlier work this paper cites.
The need for structure in quantum speedups
S. Aaronson and A. Ambainis · 2014
Cited alongside, same era.
Bosonsampling is far from uniform
S. Aaronson and A. Arkhipov · 2014
Cited alongside, same era.
Certified randomness in quantum physics
A. Acín and L. Masanes · 2016
Cited alongside, same era.
Average-case complexity versus approximate simulation of commuting quantum computations
M. J. Bremner, A. Montanaro, and D. J. Shepherd · 2016
Cited alongside, same era.
On the power of quantum fourier sampling
B. Fefferman and C. Umans · 2016
Cited alongside, same era.
Complexity-theoretic foundations of quantum supremacy experiments
S. Aaronson and L. Chen · 2017
Cited alongside, same era.
On the classical hardness of spoofing linear cross-entropy benchmarking
S. Aaronson and S. Gunn · 2020
Later among the works it cites.
Simpler proofs of quantumness
Z. Brakerski, V. Koppula, U. V. Vazirani, and T. Vidick · 2020
Later among the works it cites.
Classical verification of quantum computations with efficient verifier
N. Chia, K. Chung, and T. Yamakawa · 2020
Later among the works it cites.
Quantum computational advantage using photons
H.-S. Zhong, H. Wang, Y.-H. Deng, et al · 2020
Later among the works it cites.
A cryptographic test of quantumness and certifiable randomness from a single quantum device
Z. Brakerski, P. F. Christiano, U. Mahadev, U. V. Vazirani, and T. Vidick · 2021
Closest in time.
Noise and the frontier of quantum supremacy
A. Bouland, B. Fefferman, Z. Landau, and Y. Liu · 2021
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Tal · 2017
Cited alongside, same era.
An automatic inequality prover and instance optimal identity testing
G. Valiant and P. Valiant · 2017
Cited alongside, same era.
Forrelation: A problem that optimally separates quantum from classical computing
S. Aaronson and A. Ambainis · 2018
Cited alongside, same era.
Certified randomness from quantum supremacy
S. Aaronson · 2018
Cited alongside, same era.
Quantum supremacy and its applications
S. Aaronson · 2018
Cited alongside, same era.
Characterizing quantum supremacy in near-term devices
S. Boixo, S. V. Isakov, V. N. Smelyanskiy, et al · 2018
Cited alongside, same era.
Trading locality for time: Certifiable randomness from low-depth circuits
M. Coudron, J. Stark, and T. Vidick · 2021
Closest in time.
On the pseudo-deterministic query complexity of NP search problems
S. Goldwasser, R. Impagliazzo, T. Pitassi, and R. Santhanam · 2021
Closest in time.
Test of quantumness with small-depth quantum circuits
S. Hirahara and F. L. Gall · 2021
Closest in time.
Classically-verifiable quantum advantage from a computational bell test
G. D. Kahanamoku-Meyer, S. Choi, U. V. Vazirani, and N. Y. Yao · 2021
Closest in time.
Quantum supremacy and hardness of estimating output probabilities of quantum circuits
Y. Kondo, R. Mori, and R. Movassagh · 2021
Closest in time.
Quantum computational advantage via 60-qubit 24-cycle random circuit sampling
Q. Zhu, S. Cao, F. Chen, et al · 2021
Closest in time.
Phase-programmable gaussian boson sampling using stimulated squeezed light
H.-S. Zhong, Y.-H. Deng, J. Qin, et al · 2021
Closest in time.
H. Krovi · 2022
Closest in time.
Depth-efficient proofs of quantumness
Z. Liu and A. Gheorghiu · 2022
Closest in time.
A stochastic calculus approach to the oracle separation of 𝖡𝖰𝖯 \mathsf{BQP} and 𝖯𝖧 \mathsf{PH}
X. Wu · 2022
Closest in time.
Certified randomness from quantum supremacy
S. Aaronson and S. Hung · 2023
Closest in time.
Limitations of linear cross-entropy as a measure for quantum advantage
X. Gao, M. Kalinowski, C.-N. Chou, et al · 2024
Closest in time.
Verifiable quantum advantage without structure
T. Yamakawa and M. Zhandry · 2024
Closest in time.