Fetching the paper…
Reading the bibliography…
These are lecture notes from a weeklong course in quantum complexity theory taught at the Bellairs Research Institute in Barbados, February 21-25, 2016.
The two-valued iterative systems of mathematical logic
E. L. Post · 1941
Earlier work this paper cites.
Computational methods in the study of permutation groups
C. Sims · 1970
Earlier work this paper cites.
Conjugate coding
S. Wiesner · 1970
Earlier work this paper cites.
Quantum cryptography, or unforgeable subway tokens
C. H. Bennett, G. Brassard, S. Breidbart, and S. Wiesner · 1982
Earlier work this paper cites.
The complexity of approximate counting (preliminary version)
L. J. Stockmeyer · 1983
Earlier work this paper cites.
On the complexity of matrix group problems I
L. Babai and E. Szemerédi · 1984
Earlier work this paper cites.
How to construct random functions
O. Goldreich, S. Goldwasser, and S. Micali · 1984
Earlier work this paper cites.
Games against nature
C. H. Papadimitriou · 1985
Earlier work this paper cites.
On hiding information from an oracle
M. Abadi, J. Feigenbaum, and J. Kilian · 1989
Earlier work this paper cites.
A hard-core predicate for all one-way functions
O. Goldreich and L. A. Levin · 1989
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
S. Toda · 1989
Earlier work this paper cites.
One-way functions are necessary and sufficient for secure signatures
J. Rompel · 1990
Earlier work this paper cites.
Local expansion of vertex-transitive graphs and random generation in finite groups
L. Babai · 1991
Earlier work this paper cites.
One-way functions, hard on average problems, and statistical zero-knowledge proofs (extended abstract)
R. Ostrovsky · 1991
Earlier work this paper cites.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Quantum mechanical interaction-free measurements
A. C. Elitzur and L. Vaidman · 1993
Earlier work this paper cites.
Gap-definable counting classes
S. A. Fenner, L. J. Fortnow, and S. A. Kurtz · 1994
Earlier work this paper cites.
Natural proofs
A. A. Razborov and S. Rudich · 1994
Earlier work this paper cites.
Experimental realization of any discrete unitary operator
M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani · 1994
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1994
Earlier work this paper cites.
On the power of quantum computation
D. Simon · 1994
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Quantum measurements and the abelian stabilizer problem, 1996
A. Kitaev · 1996
Earlier work this paper cites.
Reversible space equals deterministic space
K. J. Lange, P. McKenzie, and A. Tapp · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
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.
P = bpp if e requires exponential circuits: Derandomizing the xor lemma
R. Impagliazzo and A. Wigderson · 1997
Earlier work this paper cites.
The Fabric of Reality
D. Deutsch · 1998
Earlier work this paper cites.
A pseudorandom generator from any one-way function
J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby · 1999
Earlier work this paper cites.
Super-polynomial versus half-exponential circuit size in the exponential hierarchy
P. B. Miltersen, N. V. Vinodchandran, and O. Watanabe · 1999
Earlier work this paper cites.
Coding theorem and strong converse for quantum channels
A. Winter · 1999
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
A. Ambainis · 2000
Cited alongside, same era.
Parallelization, amplification, and exponential-time simulation of quantum interactive proof systems
A. Kitaev and J. Watrous · 2000
Cited alongside, same era.
Succinct quantum proofs for properties of finite groups
J. Watrous · 2000
Cited alongside, same era.
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
M. Jerrum, A. Sinclair, and E. Vigoda · 2001
Cited alongside, same era.
Quantum lower bound for the collision problem
S. Aaronson · 2002
Cited alongside, same era.
Efficient discrete approximations of quantum gates
A. W. Harrow, B. Recht, and I. L. Chuang · 2002
Cited alongside, same era.
Breaking and making quantum money: toward a new quantum cryptographic protocol
A. Lutomirski, S. Aaronson, E. Farhi, D. Gosset, A. Hassidim, J. Kelner, and P. Shor · 2010
Later among the works it cites.
An online attack against Wiesner’s quantum money
A. Lutomirski · 2010
Later among the works it cites.
The computational complexity of linear optics
S. Aaronson and A. Arkhipov · 2011
Later among the works it cites.
Characterization of universal two-qubit hamiltonian
A. M. Childs, D. Leung, L. Mančinska, and M. Ozols · 2011
Later among the works it cites.
QIP = PSPACE
R. Jain, Z. Ji, S. Upadhyay, and J. Watrous · 2011
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Classical and Quantum Computation
A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi · 2002
Cited alongside, same era.
Computational capacity of the universe
S. Lloyd · 2002
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
Y. Shi · 2002
Cited alongside, same era.
Adiabatic quantum state generation and statistical zero knowledge
D. Aharonov and A. Ta-Shma · 2003
Cited alongside, same era.
A complete problem for statistical zero knowledge
A. Sahai and S. P. Vadhan · 2003
Cited alongside, same era.
Multilinear formulas and skepticism of quantum computing
S. Aaronson · 2004
Cited alongside, same era.
F. Pastawski, N. Y. Yao, L. Jiang, M. D. Lukin, and J. I. Cirac · 2011
Later among the works it cites.
Quantum money from hidden subspaces
S. Aaronson and P. Christiano · 2012
Later among the works it cites.
E. Farhi, D. Gosset, A. Hassidim, A. Lutomirski, and P. Shor · 2012
Later among the works it cites.
Achieving the Han-Kobayashi inner bound for the quantum interference channel
P. Sen · 2012
Later among the works it cites.
How to construct quantum random functions
M. Zhandry · 2012
Later among the works it cites.
Black holes: complementarity or firewalls?
A. Almheiri, D. Marolf, J. Polchinski, and J. Sully · 2013
Later among the works it cites.
Quantum computation vs. firewalls
D. Harlow and P. Hayden · 2013
Later among the works it cites.
Cool horizons for entangled black holes
J. Maldacena and L. Susskind · 2013
Later among the works it cites.
Inverting well conditioned matrices in quantum logspace
A. Ta-Shma · 2013
Later among the works it cites.
Quantum information theory
M. M. Wilde · 2013
Later among the works it cites.
Sequential decoding of a general classical-quantum channel
M. M. Wilde · 2013
Later among the works it cites.
A note on the quantum collision problem for random functions
M. Zhandry · 2013
Later among the works it cites.
PostBQP Postscripts: A Confession of Mathematical Errors
S. Aaronson · 2014
Later among the works it cites.
A full characterization of quantum advice
S. Aaronson and A. Drucker · 2014
Later among the works it cites.
Generation of universal linear optics by any beam splitter
A. Bouland and S. Aaronson · 2014
Later among the works it cites.
An adaptive attack on Wiesner’s quantum money based on interaction-free measurement
D. Nagaj and O. Sattath · 2014
Later among the works it cites.
Firewalls and flat mirrors: An alternative to the amps experiment which evades the harlow-hayden obstacle
J. Oppenheim and B. Unruh · 2014
Later among the works it cites.
Complexity and shock wave geometries
D. Stanford and L. Susskind · 2014
Later among the works it cites.
The classification of reversible bit operations
S. Aaronson, D. Grier, and L. Schaeffer · 2015
Later among the works it cites.
Quantum vs classical proofs and subset verification
B. Fefferman and S. Kimmel · 2015
Later among the works it cites.
Quantum union bounds for sequential projective measurements
J. Gao · 2015
Later among the works it cites.
Non-monotonicity of trace distance under tensor products
J. Maziero · 2015
Later among the works it cites.
Algebraic cryptanalysis of a quantum money scheme: the noise-free case
M. C. Pena, J. C. Faugère, and L. Perret · 2015
Later among the works it cites.
Graph isomorphism in quasipolynomial time [extended abstract]
L. Babai · 2016
Closest in time.
Complexity classification of two-qubit commuting hamiltonians
A. Bouland, L. Mančinska, and X. Zhang · 2016
Closest in time.
Sequential measurements, disturbance and property testing, 2016
A. Harrow and A. Montanaro · 2016
Closest in time.