Review of quantum circuit modelReversible ComputationRandomized computationCS 294-2 Reversibility, Accuracy 1/29/07Spring 2007 Lecture 41 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 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, Spring 2007, Lecture 4 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)xxjunk0RCRC0COPY3 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θCS 294-2, Spring 2007, Lecture 4 2When we implement a gate, how accurate does it need to be? Do we need infinite precision to build thisgate properly? A paper by Shamir, “How To Factor On Your Calculator,” shows that if we assume infiniteprecision arithmetic, then some NP complete problems can be solved in polynomial time. However, weobviously cannot have infinite precision, so we must digitize quantum computation in order to approximatevalues such as 1/√2. It turns out that logn bits of precision are necessary.Suppose we want to build a gate that rotates the input byθ, but the best accuracy we can actually build isrotation byθ±∆θ(finite precision). Let U1,...,Umbe a set of ideal gates that implement an exact rotationbyθ. Let V1,...,Vmbe a set of actual (constructible) gates that implement rotation byθ±∆θ. Letφbethe initial state. Letψbe the ideal outputψ= U1U2···Umφ,and letψ0be the actual outputψ0= V1V2···Vmφ.The closerψandψ0are to each other, the better the approximation. If we can approximate each gateto withinε= O(1/m), then we can approximate the entire circuit with small constant error.Theorem 4.1: If kUi−Vik ≤ε4mfor 1 ≤i ≤ m, then kψ−ψ0k ≤ε4.Proof:Consider the two hybrid statesψk= U1···Uk−1Vk···Vmφ, andψk+1= U1···UkVk+1···Vmφ.Subtractφk+1fromφkto getφk−φk+1= U1···Uk−1(Vk−Uk)Vk+1···VmφSince the unitary transformations don’t change the norm of the vector, the only term we need to consider isUk+1−Vk+1. But we have an upper bound on this, so we can conclude thatkψk−ψk+1k ≤ε4m.Another way to see this is the following picture. Applying unitary transformations to Umφand Vmφpreserves the angle between them, which is defined to be the norm.φU1···Um−1UmφU1···Um−1VmφVmφUmφεεCS 294-2, Spring 2007, Lecture 4 3We use the triangle inequality to finish to proof.kψ−ψ0k = kψ0−ψmk≤m−1∑i=0kφi−φi+1k≤ m·ε4m≤ε4.CS 294-2, Spring 2007, Lecture 4
View Full Document
Unlocking...