DOC PREVIEW
Berkeley COMPSCI 294 - BQP vs. P, BPP, Accuracy

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 Ux=uand Uy=u,thenx= U−1u=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 scratch0qubits.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 from0inputs. A simple solution is to apply the Hadamard gate to each0andthen measure. The Hadamard gate converts0to1√20+1√21. Measuring will result is either0or1with equal probability.µ0 w.p.121 w.p.12H1√20+1√21If 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√20+1√211−→H −→1√20−1√21No interference occurs here. Unfortunately, interference can lead to the following undesirable situation inwhich the randomness disappears:1√20+1√21) −→H −→0Measurement 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 later00µ1√20+1√21HWe 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 either0or1, 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

Berkeley COMPSCI 294 - BQP vs. P, BPP, Accuracy

Documents in this Course
"Woo" MAC

"Woo" MAC

11 pages

Pangaea

Pangaea

14 pages

Load more
Download BQP vs. P, BPP, Accuracy
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view BQP vs. P, BPP, Accuracy and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view BQP vs. P, BPP, Accuracy 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?