If you have multiple qubits, they can become entangled with each other, meaning (roughly speaking) that their measurement probabilities are no longer independent. So, for example, if we have two entangled qubits, the states and could each have probability , while the other two states have probability . If you somehow knew that their states were entangled in this way, then measuring only one qubit would tell you the value of the other -- although there would be no way to predict the value of either qubit before taking the measurement. If we have a quantum register of qubits, then each of its possible states effectively have distinct complex amplitudes. The vector of all of these complex amplitudes is our state vector, which completely encodes the statistical behavior of measurements of the system.
So now we have quantum registers, to store our information. In order to perform computations, we need quantum gates. These gates are simply unitary linear operators acting on the state vector. In order to talk about quantum time classes in a meaningful way, however, we need to restrict the set of allowable fundamental gates. (Since the composition of two unitary operators is also a unitary operator, you could design a single gate that would carry out any desired computation!) One common circuit basis involves only two fundamental gates. The first is the Hadamard gate, which takes
and
The second is the Toffoli gate, which takes three bits as input, passes through the first two bits unmodified, and XORs the third bit with the product of the first two.
Note that the fact that all changes in the state happen due to unitary operators implies that the number of outputs qubits is always equal to the number of input qubits. When dealing with quantum computation, we can assume without loss of generality that the quantum register has only a single accepting state.
Definition: BQP is the quantum analog of BPP. (Quantum computation is inherently probabilistic.) It is the class of languages decidable by polynomial-size quantum circuits that (to enforce uniformity) can be generated in polytime by a classical TM, accepting with probability at least for and with probability less than for . (Amplification theorems with similar results to those for BPP hold here, so any values and will work.)
How powerful is BQP? On the lower end, we know : we can efficiently simulate classical circuits by quantum circuits. The Toffoli gate is universal for classical computation; if you hardwire the third input to it is simply a NAND gate. Coin flips can be simulated by Hadamard gates, since they transform pure states into equal superpositions.
What about upper bounds? Clearly , since we can simulate any BQP machine by applying a polynomial number of linear operators to the exponential-size density matrix. It's also true, but less obvious, that . We can show this by integrating over computational "paths". Recall that in a quantum computation, we apply a new small unitary operator to our state at each time step. For each accepting state at time , we can compute that state's amplitude by applying the operator to each predecessor state and summing the results. By recursive application of this same step, we can compute the amplitude of any state anywhere in the computation at any time in polynomial space (although we do require exponential time).
But we can do better, namely .
Definition: GapP is the set of functions such that, for some polynomial time NTM , is the difference between the number of accepting and rejecting paths in . Note that this gives us an alternative definition for PP: a language is in PP if and only if there is some GapP function such that when , , and when , .
Fact: GapP is closed under negation, (exponential) sum, and (polynomial) product.
Fact: If there exist two GapP functions describing the real and complex parts of the entries of a polynomial sequence of complex-valued matrices, then there also exist two GapP functions describing their product.
More precisely (statement due to Watrous): let and be polynomial bounded functions, and, for each , be a sequence of complex-valued matrices of size less than . Then, if we have functions
in GapP, then there also exist functions and in GapP such that
Observe that, applying an appropriate topological ordering to our quantum circuit, we can serialize our quantum gates into a polynomial number of steps. Additionally, observe that we can take the tensor product of a gate's matrix with the identity matrix for the unaffected bits in order to come up with a complete transition matrix for each time step. We can now use this fact to show that there are functions and in GapP describing all of our quantum gates.
In order to do this, we need to take advantage of an alternate representation of our quantum register: its density matrix, . Glossing over some details, this effectively linearizes our state and operations. With entries in the state vector, the corresponding density matrix is a matrix with trace 1. The 'th entry on the diagonal is simply the probability of finding the register in state . If we then let our state be this matrix, flattened into a vector, , the entries of the matrices describing our quantum gates fall in the set . By the fact that these matrices can be generated in polynomial time, we know that the corresponding and for each matrix (multiplied by 2, to deal with the factors of 1/2) must be in GapP. Then, by the fact noted above, there must exist and describing the entries of the transition matrix for the entire circuit (multiplied by ).
We can assume that the circuit has only a single accepting state, so finding the acceptance probability is then simply a matter of looking up the single matrix entry that describes the transition from the starting state to the accepting state, which consists of a single invocation of a GapP function.
To complete the proof, note that the function is positive when accepts , and negative otherwise. Therefore can be simulated by a PP machine, and .
In fact, not only does PP contain BQP, but .
It is unknown whether this inclusion is tight, but all signs seem to indicate that it is. We can define the class QMA analogously to MA, except that Arthur is a BQP machine, and Merlin sends him quantum advice. This class, which obviously contains BQP, is contained in PP (originally noted by Kitaev and Watrous). Furthermore, a theorem of Vyalyi states that if , then .
No comments:
Post a Comment
Note: Only a member of this blog may post a comment.