row index i it is possible to efficiently find all the nonzero Aij. These restrictions make it possible in principle to solve exponentially large systems of equations in polynomial time. However, there is an important caveat: The runtime of the algorithm also scales with the condition number of A, a parameter which is related to the numerical instability of solving the system of equations classically. Finding a natural scenario in which this algorithm can be used remains a compelling open problem.

Another recent algorithmic development is a quantum analogue of the Metropolis sampling algorithm [ 2]. Classically, the Metropolis method is a technique for sampling from hard-to-analyze distributions over exponentially large state spaces (indeed, exponential speedup via use of randomness is an old example of how powerful a change of computational model can be). Its amazing range of applications includes statistical inference and approximation algorithms for the permanent of a nonnegative matrix, but it was originally developed to sample from the thermal distribution of a physical system. If state x has energy E(x), then the thermal distribution at temperature T assigns x probability proportional to e-E(x)/T, so that lower temperatures push the system harder into low-energy configurations.

The quantum Metropolis algorithm, by analogy, produces quantum states in thermal distributions. Like its classical cousin, the quantum Metropolis algorithm takes longer to produce lower-temperature states, as this corresponds to solving harder optimization problems, but proving rigorous bounds on its runtime is difficult in all but a handful of cases. Without formal proofs, we can nevertheless run the classical Metropolis algorithm and observe empirically that it works quickly in many cases of interest. An empirical evaluation of the quantum Metropolis will of course have to wait for the arrival of a large-scale quantum computer. But we may already have enough tools, if we can just figure out how to combine them to develop new quantum algorithms that use quantum Metropolis as a subroutine, just as the classical algorithm for the permanent used

Physics, Algorithms and Complexity: An Example Some physical excitations, like photons or the vibrations of a solid, can have arbitrarily low energy as their frequency gets lower and lower. Others, like extra electrons moving through semiconductors, only exist above some threshold (e.g. ,in Silicon, 1. 1 electron-Volt). The least amount of energy added by an excitation corresponds to the gap between the lowest energy level of a system and the second-lowest level.

classical Metropolis.

New proposed uses for quantum
computers continue to arise. One ex-
citing development is the increasing
number of applications being found
for quantum computers with 10 or so
qubits; small enough to be easily simu-
latable classically, while large enough
to interact in ways not previously dem-
onstrated. Such quantum computing
devices could be used to improve pre-
cision quantum measurements (e.g.