Transcription
DAC 2003: Session 51.1Tutorial: Basic Conceptsin Quantum CircuitsJohn P. HayesAdvanced Computer Architecture LaboratoryEECS DepartmentUniversity of Michigan,Ann Arbor, MI 48109, USAOutline MotivationQuantum vs. ClassicalQuantum GatesQuantum CircuitsPhysical Implementation1
Outline MotivationQuantum vs. ClassicalQuantum GatesQuantum CircuitsPhysical ImplementationComputational Limits Some important computational problemsseem to be permanently intractable Their complexity grows exponentially with problemsize, e.g. factoring large numbers—the basis for“unbreakable” Internet codes Performance improvements in “classical”computer circuits may be approaching a limit This is described by Moore’s Law2
Computational Limits Question: Is there a faster and more compact way to compute?Answer: Yes !Quantum mechanics can form the basis foran entirely new type of computation—ifquantum computing —some hugepractical implementation problems can besolvedQuantum Information A classical logic state can be 0 or 1, but not bothA quantum state can be 0 and 1 at thesame time!More precisely, a quantum state is asuperposition of the zero and one states calleda qubitc0 0 c1 1The coefficients c0 and c1 are complex numberscalled (probability) amplitudes3
Quantum Information010 1Quantum Information The Good News N qubits can store 2N binary numberssimultaneously, suggesting massive parallelismN 2: Ψ c0 00 c1 01 c2 10 c3 11or, in general, nΨ 2 1i 0ci bi, n 1bi,n 2 bi,0 Quantum states have wavelike propertiesthat allow powerful nonclassical operations(interference, entanglement)4
Quantum Information The Good News N qubits can store 2N binary numberssimultaneously, suggesting massive parallelismN 2: Ψ c0 00 c1 01 c2 10 c3 11or, in general,nΨ 2 1i 0ci bi, n 1bi,n 2 bi,0 Quantum states have wavelike propertiesthat allow powerful nonclassical operations(interference, entanglement)Quantum Information The Bad News Measurement yields just one of the 2Nsuperimposed numbers bi,n–1 bi, n–2 bi,0and destroys the superposition Quantum states are very fragile due to- Tiny (nano) scale and low energy levels- Interaction with the environment (decoherence) Implications Physical quantum circuits are extremely hard to build Fault-tolerant design is believed to be essential5
Quantum ComputingQubitregisterBasic (gate)operation 1QubitregisterBasic (gate)operation 2QubitregisterA Little History 1982: Richard Feynman suggested quantummechanics could provide an exponential speed-upin simulation1985: David Deutsch described a simple algorithmexhibiting quantum parallelism1994: Peter Shor showed how to factor integers intoprimes in polynomial time using quantum methods,thus “breaking” RSA encryption1996-now: First quantum computing devices builtat LANL, Oxford, etc. employing a few ( 10) qubits6
Outline MotivationQuantum vs. ClassicalQuantum GatesQuantum CircuitsThe FutureClassical Logic Circuits Behavior is governed implicitly by classical physics:no restrictions on copying or measuring signalsSignal states are simple bit vectors,e.g. X 01010111Signal operations are defined by Boolean algebraSmall well-defined sets of universal gate types exist ,e.g. {NAND}, {AND, OR, NOT}Circuits use fast, scalable and macroscopictechnologies such as transistor-based CMOSintegrated circuits7
Quantum Circuits Behavior is governed by quantum mechanicsSignal states are qubit vectorsOperations are defined by linear algebra over Hilbertspace and represented by unitary matrices Gates and circuits must be reversible (information-lossless) Number of output lines Number of input lines States cannot be copied so fan-out (“cloning”) is not allowed Many universal gate sets and physical implementationtechnologies exist (the best ones are not obvious)Classical vs. Quantum Circuits Example: Classical Half Adder Compute the sum and carry for two bits x1,x0x1x010011sum 0XORgatecarryANDgate8
Classical vs. Quantum Circuits Example: Quantum Half Adder Compute the sum and carry for two qubits x1,x0x1x1x0sum0carryToffoligateCNOTgateOutline MotivationQuantum vs. ClassicalQuantum GatesQuantum CircuitsPhysical Implementation9
Quantum Gates One-Inputgate: NOT Input state: c0 0 c1 1 Output state: c1 0 c0 1 Graphic symbol:X Basic states 0 and 1 are mapped thus: 0 1 1 0Quantum Gates NOT gate (contd.)0 Vector notation for states:10 Matrix notation for gate operation:1 010 11 0 Gate connection corresponds to matrixmultiplication:0 1 0 11 0 1 0 1 00 1XX ––Identity matrixNOT matrix10
Quantum Gates Hadamard Gate1 1 12 1 1H Maps 0 1/ 2 0 1/ 2 1 and 1 1/ 2 0 – 1/ 2 1so it “randomizes” the basic states1 01 1 1 1 1 1 0 12 1 1 2 1 1HH ––Quantum Gates Phase-Shift Gate1 00 e iφφ Maps 0 0 and 1 eiφ 1 so it “twists”the 1 state by an angle φ If π, it maps 1 – 1 Note that the entries of a gate matrix can becomplex numbers11
Quantum Gates Two-Input Gate: Controlled NOT (CNOT) xCNOT y x1 00 10 00 0 x x x y0 00 00 11 0 y x y CNOT maps x 0 x xand x 1 x NOT(x)Quantum Gates“Standard” Universal Gate Set1 00 00 10 00 00 10 01 0CNOT1 1 12 1 11 01000e iπ / 4HPHadamardPhaseiTT (π/8 ) gate12
Outline MotivationQuantum vs. ClassicalQuantum GatesQuantum CircuitsPhysical ImplementationQuantum Circuits A quantum “circuit” is a sequence of quantum “gates”The signals (qubits) may be static while thegates are dynamicThe circuit has fixed “width” corresponding to thenumber of qubits being processedLogic design (classical and quantum) attempts to findcircuit structures for needed operations that are Functionally correct Independent of physical technology Low-cost, e.g. uses the minimum number of qubits or gates13
Quantum Circuits Example 1: Quantum Half Adder Compute the sum and carry for two qubits x1,x0Data in x1 x1Data in x0sumData out y y carryData outControl inToffoligateControl outCNOTgateQuantum CircuitsExample 2: Implementing Deutsch’s Algorithm Problem: Determine whether a one-variable Boolean function f(x) is constant, i.e. f(0) f(1), or balanced,i.e. f(0) f(1).Classical algorithms require two evaluations of f.This algorithm uses just one quantum evaluation by,in effect, computing f(0) and f(1)simultaneouslyCircuit:HxHyUfxHMy f(x)14
Quantum Circuits Deutsch’s Algorithm (contd.) 0 1 H Ψ0x Ψ1HyUfy f(x)MHx Ψ2 Ψ3 0 constant; 1 balancedInitialize with Ψ0 01Create superposition of x states using the firstHadamard (H) gate. Set y control input usingthe second H gateCompute f(x) using the special unitary circuit UfInterfere the Ψ2 states using the third H gateMeasure the x qubitQuantum Computation Generic Structure to Compute F(X)onSuperimposeinputvectors {Xi}ComputeF(X)Interferethe resultsMeasuretheoutcomeom15
Outline MotivationQuantum vs. ClassicalQuantum GatesQuantum CircuitsPhysical ImplementationPhysical ImplementationMain Contenders Nuclear magnetic resonance (NMR) Ion traps Semiconductor quantum dots Optical latticesetc.Main Deficiency Poor scalability16
Ion Traps String of charged particles is trapped by a combinationof static and oscillating electric fields in a high-vacuumdevice Each ion has two long-lived electrical statesrepresenting 0 and 1The individual ions can be addressed by laser beamsMeans exist for initializing (optical pumping and lasercooling) and measuring the quantum state Ion TrapsChris Monroe,University ofMichigan2 µm17
Summary: State of the Art Quantum circuits can solve some important problemswith exponentially fewer operations than classicalalgorithms Small quantum circuits have been demonstrated in thelab using various physical technologies Quantum cryptography has been demonstrated overlong distances Current technologies are fragile, and appear to belimited to tens of qubits and hundreds of gates Big gaps remain in our understanding of quantum circuitand algorithm design, as well as the necessaryimplementation techniques18
7 Outline Motivation Quantum vs. Classical Quantum Gates Quantum Circuits The Future Classical Logic Circuits Behavior is governed implicitly by classical physics: no restrictions on copying or measuring signals Signal states are simple bit vectors, e.g. X 01010111 Signal operations are defined by Boolea
