Fetching the paper…
Reading the bibliography…
$\mathsf{StoqMA}$ captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem.
Trading group theory for randomness
László Babai · 1985
Earlier work this paper cites.
Private coins versus public coins in interactive proof systems
Shafi Goldwasser and Michael Sipser · 1986
Earlier work this paper cites.
On completeness and soundness in interactive proof systems
Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis Zachos · 1989
Earlier work this paper cites.
Quantum 𝖭𝖯 \mathsf{NP}
Alexei Kitaev · 1999
Earlier work this paper cites.
Succinct quantum proofs for properties of finite groups
John Watrous · 2000
Earlier work this paper cites.
Quantum fingerprinting
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf · 2001
Earlier work this paper cites.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp · 2002
Earlier work this paper cites.
In search of an easy witness: Exponential time vs. probabilistic polynomial time
Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson · 2002
Earlier work this paper cites.
Classical and quantum computation
Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi · 2002
Earlier work this paper cites.
Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
Adam R Klivans and Dieter van Melkebeek · 2002
Earlier work this paper cites.
Quantum computation and quantum information, 2002
Michael A Nielsen and Isaac Chuang · 2002
Earlier work this paper cites.
A complete problem for statistical zero knowledge
Amit Sahai and Salil Vadhan · 2003
Earlier work this paper cites.
"non-identity-check" is 𝖰𝖬𝖠 \mathsf{QMA} -complete
Dominik Janzing, Pawel Wocjan, and Thomas Beth · 2005
Earlier work this paper cites.
Derandomizing arthur–merlin games using hitting sets
Peter Bro Miltersen and N Variyam Vinodchandran · 2005
Earlier work this paper cites.
Merlin-arthur games and stoquastic complexity
Sergey Bravyi, Arvid J Bessen, and Barbara M Terhal · 2006
Earlier work this paper cites.
Error-bounded probabilistic computations between 𝖬𝖠 \mathsf{MA} and 𝖠𝖬 \mathsf{AM}
Elmar Böhler, Christian Glaßer, and Daniel Meister · 2006
Cited alongside, same era.
The complexity of stoquastic local hamiltonian problems
Sergey Bravyi, David P Divincenzo, Roberto Oliveira, and Barbara M Terhal · 2008
Cited alongside, same era.
Testing monotone high-dimensional distributions
Ronitt Rubinfeld and Rocco A Servedio · 2009
Cited alongside, same era.
Complexity of stoquastic frustration-free hamiltonians
Sergey Bravyi and Barbara Terhal · 2010
Cited alongside, same era.
Exact non-identity check is 𝖭𝖰𝖯 \mathsf{NQP} -complete
Yu Tanaka · 2010
Cited alongside, same era.
Matrix analysis
Roger A Horn and Charles R Johnson · 2012
Cited alongside, same era.
Which distribution distances are sublinearly testable?
Constantinos Daskalakis, Gautam Kamath, and John Wright · 2018
Later among the works it cites.
A complete characterization of unitary quantum space
Bill Fefferman and Cedric Yen-Yu Lin · 2018
Later among the works it cites.
Tutorial on the quantikz package
Alastair Kay · 2018
Later among the works it cites.
Statistical difference beyond the polarizing regime
Itay Berman, Akshay Degwekar, Ron D Rothblum, and Prashant Nalini Vasudevan · 2019
Later among the works it cites.
A quantum-inspired classical algorithm for recommendation systems
Ewin Tang · 2019
Later among the works it cites.
𝖲𝗍𝗈𝗊𝖬𝖠 \mathsf{StoqMA} vs. 𝖬𝖠 \mathsf{MA} : the power of error reduction
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Testing probability distributions underlying aggregated data
Clément Canonne and Ronitt Rubinfeld · 2014
Cited alongside, same era.
Strong equivalence of reversible circuits is 𝖼𝗈𝖭𝖯 \mathsf{coNP} -complete
Stephen P Jordan · 2014
Cited alongside, same era.
Monte carlo simulation of stoquastic hamiltonians
Sergey Bravyi · 2015
Cited alongside, same era.
Complexity classification of local hamiltonian problems
Toby Cubitt and Ashley Montanaro · 2016
Cited alongside, same era.
Space-efficient error reduction for unitary quantum computations
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and Harumichi Nishimura · 2016
Cited alongside, same era.
The complexity of estimating min-entropy
Thomas Watson · 2016
Cited alongside, same era.
Dorit Aharonov, Alex B Grilo, and Yupan Liu · 2020
Closest in time.
Quantum lower bounds for approximate counting via laurent polynomials
Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler · 2020
Closest in time.
Quantum approximate counting, simplified
Scott Aaronson and Patrick Rall · 2020
Closest in time.
A survey on distribution testing: Your data is big. but is it blue?
Clément L Canonne · 2020
Closest in time.
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang · 2020
Closest in time.
Private communication, 2020
Alex B. Grilo · 2020
Closest in time.
The untold story of 𝖲𝖡𝖯 \mathsf{SBP}
Ilya Volkovich · 2020
Closest in time.
Two combinatorial ma-complete problems
Dorit Aharonov and Alex B Grilo · 2021
Closest in time.
Quantum approximate counting with nonadaptive grover iterations
Ramgopal Venkateswaran and Ryan O’Donnell · 2021
Closest in time.