Fetching the paper…
Reading the bibliography…
This paper investigates the power of polynomial-time quantum computation in which only a very limited number of qubits are initially clean in the |0> state, and all the remaining qubits are initially in the totally mixed state.
PP \mathrm{PP} is as hard as the polynomial-time hierarchy
Seinosuke Toda · 1991
Earlier work this paper cites.
Counting classes are at least as hard as the polynomial-time hierarchy
Seinosuke Toda and Mitsunori Ogiwara · 1992
Earlier work this paper cites.
Probabilistic polynomials, AC 0 \mathrm{AC}^{0} functions and the polynomial-time hierarchy
Jun Tarui · 1993
Earlier work this paper cites.
Elementary gates for quantum computation
Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter · 1995
Earlier work this paper cites.
Quantum computability
Leonard M. Adleman, Jonathan DeMarrais, and Ming-Deh A. Huang · 1997
Earlier work this paper cites.
1-way quantum finite automata: strengths, weaknesses and generalizations
Andris Ambainis and Rūsiņš Freivalds · 1998
Earlier work this paper cites.
Power of one bit of quantum information
E. Knill and R. Laflamme · 1998
Earlier work this paper cites.
Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
Stephen Fenner, Frederic Green, Steven Homer, and Randall Pruim · 1999
Earlier work this paper cites.
A new universal and fault-tolerant quantum basis
P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani Roychowdhury, and Farrokh Vatan · 2000
Earlier work this paper cites.
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
Alexei Kitaev and John Watrous · 2000
Earlier work this paper cites.
Quantum Computation and Quantum Information
Michael A. Nielsen and Isaac L. Chuang · 2000
Earlier work this paper cites.
Quantum simulations of classical random walks and undirected graph connectivity
John Watrous · 2001
Earlier work this paper cites.
Classical and Quantum Computation , volume 47 of Graduate Studies in Mathematics
Alexei Yu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi · 2002
Earlier work this paper cites.
Testing integrability with a single bit of quantum information
David Poulin, Raymond Laflamme, G. J. Milburn, and Juan Pablo Paz · 2003
Cited alongside, same era.
Exponential speedup with a single bit of quantum information: Measuring the average fidelity decay
David Poulin, Robin Blume-Kohout, Raymond Laflamme, and Harold Ollivier · 2004
Cited alongside, same era.
Adaptive quantum computation, constant depth quantum circuits and Arthur-Merlin games
Barbara M. Terhal and David P. DiVincenzo · 2004
Cited alongside, same era.
Quantum computing, postselection, and probabilistic polynomial-time
Scott Aaronson · 2005
Cited alongside, same era.
Computing with highly mixed states
Andris Ambainis, Leonard J. Schulman, and Umesh Vazirani · 2006
Cited alongside, same era.
Error-bounded probabilistic computations between MA \mathrm{MA} and AM \mathrm{AM}
The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov · 2013
Later among the works it cites.
Commuting quantum circuits: Efficient classical simulations versus hardness results
Xiaotong Ni and Maarten Van den Nest · 2013
Later among the works it cites.
Quantum Information Theory
Mark M. Wilde · 2013
Later among the works it cites.
Approximating the Turaev-Viro invariant of mapping tori is complete for one clean qubit
Stephen P. Jordan and Gorjan Alagic · 2014
Later among the works it cites.
Classical simulation complexity of extended Clifford circuits
Richard Jozsa and Maarten Van den Nest · 2014
Later among the works it cites.
Hardness of classically simulating the one-clean-qubit model
Tomoyuki Morimae, Keisuke Fujii, and Joseph F. Fitzsimons · 2014
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Elmar Böhler, Christian Glaßer, and Daniel Meister · 2006
Cited alongside, same era.
Computation with unitaries and one pure qubit
D. J. Shepherd · 2006
Cited alongside, same era.
Estimating Jones polynomials is a complete problem for one clean qubit
Peter W. Shor and Stephen P. Jordan · 2008
Cited alongside, same era.
Quantum Strategies and Local Operations
Gustav Gutoski · 2009
Cited alongside, same era.
Estimating Jones and HOMFLY polynomials with one clean qubit
Stephen P. Jordan and Pawel Wocjan · 2009
Cited alongside, same era.
Quantum Complexity : restrictions on algorithms and architectures
Daniel James Shepherd · 2009
Cited alongside, same era.
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
Michael J. Bremner, Richard Jozsa, and Dan J. Shepherd · 2011
Cited alongside, same era.
Hardness of classically simulating quantum circuits with unbounded Toffoli and fan-out gates
Yasuhiro Takahashi, Takeshi Yamazaki, and Kazuyuki Tanaka · 2014
Later among the works it cites.
Average-case complexity versus approximate simulation of commuting quantum computations
Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd · 2015
Closest in time.
The complexity of simulating constant-depth BosonSampling
Daniel J. Brod · 2015
Closest in time.
On the power of quantum Fourier sampling
Bill Fefferman and Chris Umans · 2015
Closest in time.
Stronger methods of making quantum interactive proofs perfectly complete
Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura · 2015
Closest in time.
How hard is it to approximate the Jones polynomial?
Greg Kuperberg · 2015
Closest in time.
Commuting quantum circuits with few outputs are unlikely to be classically simulatable
Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, and Kazuyuki Tanaka · 2015
Closest in time.