Fetching the paper…
Reading the bibliography…
Valiant-Vazirani showed in 1985 [VV85] that solving NP with the promise that "yes" instances have only one witness is powerful enough to solve the entire NP class (under randomized reductions).
The Complexity of Theorem-Proving Procedures
S. A. Cook · 1971
Earlier work this paper cites.
Relative Complexity of Checking and Evaluating
L. G. Valiant · 1976
Earlier work this paper cites.
Computational Complexity of Probabilistic Turing Machines
J. Gill · 1977
Earlier work this paper cites.
Universal Classes of Hash Functions
L. Carter and M. N. Wegman · 1979
Earlier work this paper cites.
Trading Group Theory for Randomness
L. Babai · 1985
Earlier work this paper cites.
NP Is as Easy as Detecting Unique Solutions
L. G. Valiant and V. V. Vazirani · 1985
Earlier work this paper cites.
Probabalistic Quantifiers vs. Distrustful Adversaries
S. Zachos and M. Fürer · 1987
Earlier work this paper cites.
Matrix Analysis
R. Bhatia · 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.
Quantum NP
A. Kitaev · 1999
Earlier work this paper cites.
A study of statistical zero-knowledge proofs
S. Vadhan · 1999
Earlier work this paper cites.
Quantum NP - A Survey, 2002, arXiv: quant-ph/0210077
D. Aharonov and T. Naveh · 2002
Earlier work this paper cites.
Classical and Quantum Computation
A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi · 2002
Earlier work this paper cites.
3-local Hamiltonian is QMA-complete
J. Kempe and O. Regev · 2003
Earlier work this paper cites.
Representation Theory
W. Fulton and J. Harris · 2004
Earlier work this paper cites.
Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
Earlier work this paper cites.
On the Power of Random Bases in Fourier Sampling: Hidden Subgroup Problem in the Heisenberg Group
J. Radhakrishnan, M. Rötteler, and P. Sen · 2005
Cited alongside, same era.
Ground-State Approximation for Strongly Interacting Spin Systems in Arbitrary Spatial Dimension
S. Anders, M. B. Plenio, W. Dür, F. Verstraete, and H.-J. Briegel · 2006
Cited alongside, same era.
Elements of information theory (2. ed.)
T. M. Cover and J. A. Thomas · 2006
Cited alongside, same era.
The Complexity of the Local Hamiltonian Problem
J. Kempe, A. Y. Kitaev, and O. Regev · 2006
Cited alongside, same era.
Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem
P. Sen · 2006
Cited alongside, same era.
Several natural BQP-Complete problems, 2006, arXiv: quant-ph/0606179
P. Wocjan and S. Zhang · 2006
Quantum Computation and Quantum Information (10th Anniversary edition)
M. A. Nielsen and I. L. Chuang · 2010
Closest in time.
On the Power of a Unique Quantum Witness
R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattath, and S. Zhang · 2012
Closest in time.
Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems
S. P. Jordan, H. Kobayashi, D. Nagaj, and H. Nishimura · 2012
Closest in time.
The local Hamiltonian problem on a line with eight states is QMA-complete
S. Hallgren, D. Nagaj, and S. Narayanaswami · 2013
Closest in time.
On Physical Problems that are Slightly More Difficult than QMA
A. Ambainis · 2014
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Quantum t-designs: t-wise Independence in the Quantum World
A. Ambainis and J. Emerson · 2007
Cited alongside, same era.
The Power of Quantum Systems on a Line
D. Aharonov, D. Gottesman, S. Irani, and J. Kempe · 2007
Cited alongside, same era.
The Importance of the Spectral Gap in Estimating Ground-State Energies
A. Deshpande, A. V. Gorshkov, and B. Fefferman · 2007
Cited alongside, same era.
Matrix product state representations
D. Pérez-García, F. Verstraete, M. M. Wolf, and J. I. Cirac · 2007
Cited alongside, same era.
Entanglement Renormalization
G. Vidal · 2007
Cited alongside, same era.
D. Aharonov, M. Ben-Or, F. G. S. L. Brandao, and O. Sattath · 2008
Cited alongside, same era.
T. S. Cubitt, D. Pérez-García, and M. M. Wolf · 2015
Closest in time.
Quantum Hamiltonian Complexity
S. Gharibian, Y. Huang, Z. Landau, and S. W. Shin · 2015
Closest in time.
A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians
Z. Landau, U. Vazirani, and T. Vidick · 2015
Closest in time.
Quantum Merlin Arthur with Exponentially Small Gap, 2016, arXiv: 1601.01975
B. Fefferman and C. Lin · 2016
Closest in time.
Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D
I. Arad, Z. Landau, U. Vazirani, and T. Vidick · 2017
Closest in time.
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma
A. P. Gilyén and O. Sattath · 2017
Closest in time.
History-state Hamiltonians are critical, 2018, arXiv: 1810.06528
C. E. González-Guillén and T. S. Cubitt · 2018
Closest in time.
The Theory of Quantum Information
J. Watrous · 2018
Closest in time.
The complexity of simulating local measurements on quantum systems
S. Gharibian and J. Yirka · 2019
Closest in time.
Undecidability of the Spectral Gap in One Dimension
J. Bausch, T. S. Cubitt, A. Lucia, and D. Perez-Garcia · 2020
Closest in time.
An area law for one-dimensional quantum systems
M. B. Hastings · 2024
Closest in time.