Fetching the paper…
Reading the bibliography…
We prove the following surprising result: given any quantum state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that any ground state of H can be used to simulate rho on all quantum circuits of fixed polynomial size.
On the density of families of sets
N. Sauer · 1972
Earlier work this paper cites.
Some estimates of the information transmitted by quantum communication channels
A. S. Holevo · 1973
Earlier work this paper cites.
Turing machines that take advice
R. M. Karp and R. J. Lipton · 1982
Earlier work this paper cites.
A theory of the learnable
L. G. Valiant · 1984
Earlier work this paper cites.
Learnability and the Vapnik-Chervonenkis dimension
A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth · 1989
Earlier work this paper cites.
The strength of weak learnability
R. E. Schapire · 1990
Earlier work this paper cites.
Oracles and queries that are sufficient for exact learning
N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, and C. Tamon · 1994
Earlier work this paper cites.
A ‘pretty good’ measurement for distinguishing quantum states
P. Hausladen and W. K. Wootters · 1994
Earlier work this paper cites.
Hard-core distributions for somewhat hard problems
R. Impagliazzo · 1995
Earlier work this paper cites.
Scale-sensitive dimensions, uniform convergence, and learnability
N. Alon, S. Ben-David, N. Cesa-Bianchi, and D. Haussler · 1997
Earlier work this paper cites.
A decision-theoretic generalization of on-line learning and an application to boosting
Y. Freund and R. E. Schapire · 1997
Earlier work this paper cites.
Prediction, learning, uniform convergence, and scale-sensitive dimensions
P. L. Bartlett and P. M. Long · 1998
Earlier work this paper cites.
Dense quantum coding and a lower bound for 1-way quantum automata
A. Ambainis, A. Nayak, A. Ta-Shma, and U. V. Vazirani · 1999
Cited alongside, same era.
Quantum dense coding and quantum finite automata
A. Ambainis, A. Nayak, A. Ta-Shma, and U. V. Vazirani · 1999
Cited alongside, same era.
One-sided versus two-sided error in probabilistic computation
Harry Buhrman and Lance Fortnow · 1999
Cited alongside, same era.
Optimal lower bounds for quantum automata and random access codes
A. Nayak · 1999
Cited alongside, same era.
Succinct quantum proofs for properties of finite groups
J. Watrous · 2000
Cited alongside, same era.
Quantum NP - a survey
D. Aharonov and T. Naveh · 2002
Cited alongside, same era.
Lattice problems in NP intersect coNP
D. Aharonov and O. Regev · 2004
Later among the works it cites.
The complexity of the Local Hamiltonian problem
J. Kempe, A. Kitaev, and O. Regev · 2004
Later among the works it cites.
Oracles are subtle but not malicious
S. Aaronson · 2006
Later among the works it cites.
QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum protocols
S. Aaronson · 2006
Later among the works it cites.
Oblivious symmetric alternation
V. Chakaravarthy and S. Roy · 2006
Later among the works it cites.
The learnability of quantum states
S. Aaronson · 2007
Later among the works it cites.
Quantum versus classical proofs and advice
S. Aaronson and G. Kuperberg · 2007
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Classical and Quantum Computation
A. Kitaev, A. Shen, and M. N. Vyalyi · 2002
Cited alongside, same era.
A lattice problem in Quantum NP
D. Aharonov and O. Regev · 2003
Cited alongside, same era.
Polynomial time quantum computation with advice
H. Nishimura and T. Yamakami · 2003
Cited alongside, same era.
Efficient classical simulation of slightly entangled quantum computations
G. Vidal · 2003
Cited alongside, same era.
Multilinear formulas and skepticism of quantum computing
S. Aaronson · 2004
Cited alongside, same era.
Limitations of quantum advice and one-way communication
S. Aaronson · 2004
Cited alongside, same era.
Later among the works it cites.
On approximate majority and probabilistic time
E. Viola · 2007
Later among the works it cites.
Perturbative gadgets at arbitrary orders
Stephen P. Jordan and Edward Farhi · 2008
Later among the works it cites.
Learning theory lecture notes, 2008
S. Kakade and A. Tewari · 2008
Later among the works it cites.
Fixed-polynomial size circuit bounds
L. Fortnow, R. Santhanam, and R. Williams · 2009
Later among the works it cites.
The complexity of quantum spin systems on a two-dimensional square lattice
Roberto Oliveira and Barbara M. Terhal · 2010
Closest in time.