Is there an equivalent to derandomization for quantum algorithms?

Question

With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed using the fact that the theorems are about the expected performance of the random algorithm). Is there an equivalent for quantum algorithms? Are there any well-known results of "dequantization"? Or is the underlying state space too big for this sort of technique?

Answer 1

There was a blog post by Fortnow on this topic. It's believed that there's no hope of a "dequantization" program, similar to the derandomization one.

On the other hand, for some specific non-quantum results that were obtained using quantum methods, it has been possible to remove the quantumness in the proof. For example, Kerenidis and de Wolf (2002) proved the first exponential lower bound for the length of possibly non-linear 2-query locally decodable codes using quantum arguments. Later, Ben-Aroya, Regev and de Wolf (2007) could remove the quantumness of the proof (although the line of argument still modeled the quantum one). Similar situations also arose in proving lower bounds for rigidity of Hadamard matrices, and in showing that PP is closed under intersection (though in reverse chronological order :)). See this survey by Drucker and de Wolf for references and discussion.

Answer 2

There are certain classes of quantum gates which can be simulated efficiently with a classical computer. If no entanglement is present, a computation with pure states (i.e. not random states) can be simulated efficiently. Classical gates reversible gates are a subset of quantum gates, and so can obviously be simulated efficiently. These two examples are pretty trivial, however there are a number of non-trivial gate sets known.

1. Valiant gates as mentioned in Joshua's answer
2. Clifford group gates (see arXiv:quant-ph/0406196)
3. Match gates (see arXiv:0804.4050)
4. Commuting gates, etc.

Basically, most sets of operators which generate only some small subspace of $SU(2^N)$ tend to be simulable, while any that generate $SU(2^N)$ are as hard as general quantum simulation of N qubits.

It seems very unlikely that quantum mechanics is efficiently simulable, and so such a dequantization program will likely be impossible in general. There is however a regime where this has worked, which is with interactive proofs. Several different kinds of interactive proof systems with quantum verifiers have been shown to have the same power if the quantum verifier is replaced with a purely classical verifier. For an example of this, see Jain, Ji, Upadhyay and Watrous's proof that QIP=PSPACE (arXiv:0907.4737).

Answer 3

One interesting setting in which to study "dequantization" is communication complexity. Here, an interesting question is whether an upper bound can be put on the amount of entanglement that Alice and Bob need to share in order to achieve an efficient quantum protocol for solving some problem. This would be a quantum analogue of Newman's Theorem from classical communication complexity. Gavinsky has given a relational problem for which this cannot be done, but as far as I am aware this is still open for (total) functional problems.

Also, an addendum to Joe's comment about commuting gates: Bremner, Jozsa and Shepherd have recently shown (arXiv:1005.1407) that a particular notion of commuting circuits is unlikely to be simulable, as this would collapse the polynomial hierarchy to the third level.

Answer 4

Although in general "dequantization" is unlikely, I believe that this sort of idea helped inspire Valiant's holographic algorithms. Or, at the very least, you can view his work as some partial dequantization results on restricted classes of quantum circuits. See, for example: L. Valiant. Quantum Circuits That Can Be Simulated Classically in Polynomial Time. SIAM J. Comput. 31 (4) 1229-1254 (2002).