Fetching the paper…
Reading the bibliography…
Output probability distributions of several sub-universal quantum computing models cannot be classically efficiently sampled unless some unlikely consequences occur in classical complexity theory, such as the collapse of the polynomial-time hierarchy.
1902
Earlier work this paper cites.
1909
Earlier work this paper cites.
A. K. Chandra, L. J. Stockmeyer, and U. Vishkin, Constant depth reducibility. SIAM J. Comput. 13
1984
Earlier work this paper cites.
R. Beigel, Relativized counting classes: Relations among thresholds, parity, and Mods. J. of Comput. System. Sci. 42
1991
Earlier work this paper cites.
P. W. Shor, Algorithms for quantum computation: discrete logarithms and factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), p.124 (1994)
1994
Earlier work this paper cites.
D. R. Simon, On the power of quantum computation. Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), p.116 (1994)
1994
Earlier work this paper cites.
R. Beigel and J. Tarui, On ACC. Computational Complexity 4
1994
Earlier work this paper cites.
A. Gajentaan and M. Overmars, On a class of O ( n 2 ) O(n^{2}) problems in computational geometry. Computational Geometry 5
1995
Earlier work this paper cites.
A. Barenco et al., Elementary gates for quantum computation. Phys. Rev. A 52
1995
Earlier work this paper cites.
L. K. Grover, Quantum mechanics helps in searching for a needle in haystack. Phys. Rev. Lett. 79
1997
Earlier work this paper cites.
H. Buhrman, R. Cleve, and A. Wigderson, Quantum vs. classical communication and computation. Proceedings of the 30th Annual ACM Symposium on Theory of Computing, p.63 (1998)
1998
Earlier work this paper cites.
E. Knill and R. Laflamme, Power of one bit of quantum information. Phys. Rev. Lett. 81
1998
Earlier work this paper cites.
R. Raz, Exponential separation of quantum and classical communication complexity. Proceedings of the 31st Annual ACM Symposium on Theory of Computing, p.358 (1999)
1999
Earlier work this paper cites.
H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Quantum fingerprinting. Phys. Rev. Lett. 87
2001
Earlier work this paper cites.
R. Impagliazzo, R. Paturi, and F. Zane, Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63
2001
Earlier work this paper cites.
R. Impagliazzo and R. Paturi, On the complexity of k-SAT. J. Comput. Syst. Sci. 62
2001
Earlier work this paper cites.
L. G. Valiant, Quantum computers that can be simulated classically in polynomial time. Proceedings of the 33rd Annual ACM Symposium on Theory of Computing p.114 (2001)
2001
Earlier work this paper cites.
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information
2002
Cited alongside, same era.
D. Poulin, R. Laflamme, G. J. Milburn, and J. P. Paz, Testing integrability with a single bit of quantum information. Phys. Rev. A 68
2003
Cited alongside, same era.
B. M. Terhal and D. P. DiVincenzo, Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games. Quant. Inf. Comput. 4
2004
Cited alongside, same era.
D. Poulin, R. Blume-Kohout, R. Laflamme, and H. Ollivier, Exponential speedup with a single bit of quantum information: measuring the average fidelity decay. Phys. Rev. Lett. 92
2004
Cited alongside, same era.
L. Roditty and U. Zwick, On dynamic shortest paths problems. In Algorithms ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings, pages 580-591, 2004
2004
T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one clean qubit model. Phys. Rev. Lett. 112
2014
Later among the works it cites.
V. Vassilevska Williams, Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis. In Proc. International Symposium on Parameterized and Exact Computation, pages 16-28 (2015)
2015
Later among the works it cites.
M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average-case complexity versus approximate simulation of commuting quantum computations. Phys. Rev. Lett. 117
2016
Later among the works it cites.
K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Power of quantum computation with few clean qubits. Proceedings of 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), pp.13:1-13:14 (2016)
2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Y. Shi, Quantum and classical tradeoffs. Theoretical Computer Science 344
2005
Cited alongside, same era.
A. Datta, S. T. Flammia, and C. M. Caves, Entanglement and the power of one qubit. Phys. Rev. A 72
2005
Cited alongside, same era.
C. M. Dawson, H. L. Haselgrove, A. P. Hines, D. Mortimer, M. A. Nielsen, and T. J. Osborne, Quatnum computing and polynomial equations over the finite field Z 2 Z_{2} . Quant. Inf. Comput. 5
2005
Cited alongside, same era.
P. W. Shor and S. P. Jordan, Estimating Jones polynomials is a complete problem for one clean qubit. Quant. Inf. Comput. 8
2008
Cited alongside, same era.
G. Passante, O. Moussa, C. A. Ryan, and R. Laflamme, Experimental approximation of the Jones polynomial with one quantum bit. Phys. Rev. Lett. 103
2009
Cited alongside, same era.
S. P. Jordan and P. Wocjan, Estimating Jones and HOMFLY polynomials with one clean qubit. Quat. Inf. Comput. 9
2009
Cited alongside, same era.
H. Buhrman, R. Cleve, S. Massar, and R. de Wolf, Nonlocality and communication complexity. Rev. Mod. Phys. 82
2010
Cited alongside, same era.
M. L. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, S. Schneider, Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility. ITCS 2016: 261-270
2016
Later among the works it cites.
T. M. Chan and R. Williams, Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky. SODA 2016: 1246-1255
2016
Later among the works it cites.
A. Abboud, T. D. Hansen, V. V. Williams, and R. Williams, Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. STOC 2016: 375-388
2016
Later among the works it cites.
S. Bravyi and D. Gosset, Improved classical simulation of quantum circuits dominated by Clifford gates. Phys. Rev.Lett. 116
2016
Later among the works it cites.
S. Bravyi, G. Smith, and J. A. Smolin, Trading classical and quantum computational resources. Phys. Rev. X 6
2016
Later among the works it cites.
M. Cygan et al., On problems as hard as CNF-SAT. ACM Transactions on Algorithms 12
2016
Later among the works it cites.
T. Morimae, Hardness of classically sampling one clean qubit model with constant total variation distance error. Phys. Rev. A 96
2017
Later among the works it cites.
A. M. Dalzell, Bachelor thesis, MIT (2017). https://dspace.mit.edu/handle/1721.1/111859
2017
Later among the works it cites.
T. Morimae, K. Fujii, and H. Nishimura, Power of one non-clean qubit. Phys. Rev. A 95
2017
Later among the works it cites.
D. Lokshtanov, R. Paturi, S. Tamaki, R. Williams, and H. Yu, Beating brute force for systems of polynomial equations over finite fields. Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.2190-2202 (2017)
2017
Later among the works it cites.
M. Ball, A. Rosen, M. Sabin, and P. N. Vasudevan, Average-case fine-grained hardness. Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), pages 483-496
2017
Later among the works it cites.
K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Tamate, and S. Tani, Impossibility of classically simulating one-clean-qubit model with multiplicative error. Phys. Rev. Lett. 120
2018
Later among the works it cites.
T. Morimae, Y. Takeuchi, and H. Nishimura, Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy. Quantum 2
2018
Later among the works it cites.