Superpolynomial speedups based on almost any quantum circuit

Logarithmic Sobolev inequalities for finite Markov chains

P. Diaconis and L. Saloff-Coste · 1996

Earlier work this paper cites.

Quantum computation of Fourier transforms over symmetric groups

Robert Beals · 1997

Earlier work this paper cites.

The fourth moment method

Bonnie Berger · 1997

Earlier work this paper cites.

Quantum complexity theory

Ethan Bernstein and Umesh Vazirani · 1997

Earlier work this paper cites.

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

Peter W. Shor · 1997

Earlier work this paper cites.

On the power of quantum computation

Daniel R. Simon · 1997

Earlier work this paper cites.

Cryptographic distinguishability measures for quantum mechanical states

Chris A. Fuchs and Jeroen van de Graaf · 1999

Earlier work this paper cites.

Efficient quantum algorithms for some instances of the non-abelian hidden subgroup problem

Gábor Ivanyos, Frédéric Magniez, and Miklos Santha · 2001

Cited alongside, same era.

Quantum algorithms for solvable groups

John Watrous · 2001

Cited alongside, same era.

Quantum lower bound for recursive Fourier sampling

Scott Aaronson · 2003

Cited alongside, same era.

Hidden translation and orbit coset in quantum computing

Katalin Friedl, Gabor Ivanyos, Frederic Magniez, Miklos Santha, and Pranab Sen · 2003

Cited alongside, same era.

Quantum algorithms for some hidden shift problems

Wim van Dam, Sean Hallgren, and Lawrence Ip · 2003

Cited alongside, same era.

From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups

Dave Bacon, Andrew M. Childs, and Wim van Dam · 2005

A polynomial quantum algorithm for approximating the jones polynomial

Dorit Aharonov, Vaughan Jones, and Zeph Landau · 2006

Later among the works it cites.

Limitations of quantum coset states for graph isomorphism

Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, and Pranab Sen · 2006

Later among the works it cites.

The foundations of statistical mechanics from entanglement: Individual states vs. averages

Sandu Popescu, Anthony J. Short, and Andreas Winter · 2006

Later among the works it cites.

Emergence of typical entanglement in two-party random processes

Oscar C.O. Dahlsten, Roberto Oliveira, and Martin B. Plenio · 2007

Later among the works it cites.

Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem

Sean Hallgren · 2007

Later among the works it cites.

Random circuits are approximate 2-designs