Reversible ComputationP BQPSimulating Classical CircuitsProof: P BQPBPP BQPReview: BPPSimulating BPPIs Quantum Computation Digital?CS 294-2 BQP vs. P, BPP, Accuracy 9/14/04Fall 2004 Lecture 51 Reversible ComputationQuantum computation is unitary. A quantum circuit corresponds to a unitary operator U acting on n qubits.Being unitary means UU†= U†U = I. A quantum circuit which performs a unitary operation U has a mirrorimage circuit which performs the corresponding operation U†.U†gφφgUThe circuits for U and U†are the same size and have mirror image gates. Examples:H = H†CNOT = CNOT†Rθ= R†−θ2 P ⊆ BQPWe will show how any classical computation can be simulated by a quantum circuit and then show thespecific result that P is contained in BQP.2.1 Simulating Classical CircuitsQuantum computation originally (in the late 70s and early 80s) tried to understand whether unitary constrainton quantum evolution provided limits beyond those explored in classical computation. A unitary transfor-mation taking basis states to basis states must be a permutation. (Indeed, if Ux=uand Uy=u,thenx= U−1u=y.) Therefore quantum mechanics imposes the constraint that classically it must bereversible computation.How can a classical circuit C which takes an n bit input x and computes f(x) be made into a reversiblequantum circuit that computes the same function? We can never lose any information, so in general thecircuit must output both the input x and the output f(x). In addition, the quantum circuit may need someadditional scratch qubits during the computation since individual gates can’t lose any information either.The consequence of these constraints is illustrated below.CS 294-2, Fall 2004, Lecture 5 1000f(x)xf(x)xx=⇒CUHow is this done? Recall that any classical AND and OR gates can be simulated with a C-SWAP gate andsome scratch0qubits.abcC-SWAPaswap b and c iff a = 1If we construct the corresponding reversible circuit RC, we have a small problem. The CSWAP gates endup converting input scratch bits to garbage. How do we restore the scratch bits to 0 on output? We use thefact that RC is a reversible circuit. The sequence of steps for the overall circuit is(x,0k,0m,0k,1)C0−→(x,y,garbagex,0k,1)copy y−→ (x,y, garbagex,y,1)(C0)−1−→ (x,0k,0m,y,1) .Overall, this gives us a clean reversible circuitˆC corresponding to C.REVf(x)xf(x) f(x)f(x)xxjunk0RCRC0COPY2.2 Proof: P ⊆ BQPDefine a simple circuit as a reversible circuit which takes as input x and outputs f(x) and does not generate acopy of x on the output as previously described. Also, roughly define an efficient circuit as one with a smallnumber of total gates.Theorem 5.1: There exists a simple circuit for f if and only if f is a bijection and there are efficient circuitsfor f and f−1.CS 294-2, Fall 2004, Lecture 5 2Proof:If there is a simple circuit for f, then running that circuit in reverse will compute f−1(x) withoutknowledge of x. Each y has a unique pre-image under f, thus f is a bijection.To prove the converse, assume that f is a bijection. An efficient circuit for f implies the existence of anefficient reversible circuit RC1which computes f(x). An efficient circuit for f−1implies the existence ofan efficient reversible circuit RC2which computes f−1(x).f(x)xf(x)200RC100xf(x)xRCThe concatenation RC1followed by RCREV2is the desired simple circuit.A direct consequence of this theorem is that any polynomial time circuit can be simulated quantumly.3 BPP ⊆ BQPWe will show that any circuit in BPP can be simulated in BQP by first generating random qubits and thensimulating the corresponding polynomial circuit.3.1 Review: BPPBPP stands for bounded error probabilistic polynomial time. As an example, consider the language PRIMESconsisting of prime numbers. There exists a polynomial size circuit C which takes as input x and somerandom bits r and outputs 1 for ACCEPT and 0 for REJECT.0/1A/Rr(poly size)CxWe say PRIMES∈BPP ifx ∈ PRIMES ⇒ Pr{C(x,r) = 1} ≥ 2/3,x 6∈ PRIMES ⇒ Pr{C(x,r) = 0} ≥ 2/3.3.2 Simulating BPPThe main difference between a P circuit and a BPP circuit is the additional input of r random bits. Wehave already shown that any circuit in P can be simulated in BQP. We want to show that it is possible toCS 294-2, Fall 2004, Lecture 5 3generate random qubits from0inputs. A simple solution is to apply the Hadamard gate to each0andthen measure. The Hadamard gate converts0to1√20+1√21. Measuring will result is either0or1with equal probability.µ0 w.p.121 w.p.12H1√20+1√21If we generate random bits like this and then run the corresponding quantum circuit to C, we get the straight-forward circuit below.rRCx0HHHµµµMeasurement can be tricky in the intermediate stages of a quantum circuit. Why not skip the measurementand get a superposition of states? Well, if a Hadamard gate occurs in the circuit, we have a problem. Thedesired outcome is one of these two possibilities with probability 1/2:0−→H −→1√20+1√211−→H −→1√20−1√21No interference occurs here. Unfortunately, interference can lead to the following undesirable situation inwhich the randomness disappears:1√20+1√21) −→H −→0Measurement prevents quantum interference. But, by the principle of deferred measurement, we can post-pone the measurement and get the same result. In fact, we can post the measurement indefinitely and notperform it at all.much later00µ1√20+1√21HWe now need twice as many qubits as before. Half of them are passed through Hadamard gates and con-nected by CNOT gates to the other half. This fixes the first half of the qubits to either0or1, eventhough no measurement was made. It is important to note, however, that since the second half of the qubitsare now entangled with the first half, we must be certain not to make any measurements on them either.CS 294-2, Fall 2004, Lecture 5 4RC0xHHH4 Is Quantum Computation Digital?There is an issue as to whether or not quantum computing is digital. We need only look at simple gates suchas the Hadamard gate or a rotation gate to find real values.H = 1√21√21√2−1√2!Rθ=cosθ−sinθsinθcosθWhen we implement a gate, how accurate
View Full Document