From Quantum Gates to Quantum Learning reent research and 从量子大门量子学习的研究

1、from quantum gates to quantum learning: recent research and open problems in quantum circuitsmarek a. perkowski,portland quantum logic group,department of electrical engineering and computer science,korea advanced institute of science and technology, anddepartment of electrical and computer engineer

2、ing, portland state university, usa.the progress in classical computer technology has been dramatic1999 pentium iiib/transistor/science/events/pointctrans.html1947 first point contact transistorby bardeen and brattainnano-systemhow small is a nanometer? 1 meter 10 mm 1 mm 10 nm 1nan

3、ometer 0.1 nm 1 picometer 1 femtometer size of red blood cell = a millionth of a meter size of polio virus = a billionth of a meter size of the hydrogen atom = a trillionth of a meter = 10 -15 m, size of a protonnumber of atoms in a useful systemfrom r. keyes, ibm j. res. develop (1988)# atoms to st

4、ore a bit # dopant atoms/bipolar transistorhistory 1970s and 1980s, introduction of quantum computers (richard feynmann, david deutsch, and paul benioff) 1994, peter shors factoring algorithm 1996, lov grover, searching algorithm 1998, 1999, 2001 isaac l. chuang, developed the worlds first 2-qubit,

5、3-qubit, 5-qubit and 7-qubit quantum computerpeopleturing machine (1936)”“ quantum circuits(1985)”first ideas(1982)”“factorization (1997)”a. turingr. feynmannd. deutschp. shorrjiffy quantum theory quantum nature: a combination of both. in preparing the initial state: only one of the 2 states on meas

6、urement: only one state found. probability: the states component in the mix both preparation and measurement in contact with a macro system|0|1|0 and |1info unit: 1 bit. physical system: 2 statesqubit in a ion trapquantum logic circuits how a single photon behaves in a beam splitter?50%50%01beam spl

7、ittersingle photonoptical sensor strange behavior1100mach-zehnder apparatusquantum gate: square root of not0101not1100notnotsimple theory of the beam-splitter0101%50%50the simplest explanation is that the beam-splitter acts as a classical coin-flip, randomly sending each photon one way or the other.

8、quantum interference0101%100the simplest explanation must be wrong, since it would predict a 50-50 distribution.more experimental data collected to improve the theory01012cos22sin2a new theory01012cos22sin212102i12e02iithe particle can exist in a linear combination or superposition of the two paths1

9、2) 1e( i021eii-probability amplitude and measurement010120if the photon is measured when it is in the statethen we get with probability and |1 with probability 1010212001212021quantum operations are linearthe operations are induced by the apparatus linearly, that is, if andthen12i02112102i1010101210

10、2i012i021112i210212i1010quantum operations are unitaryany linear operation that takes statessatisfyingand maps them to statessatisfyingmust be unitary121201010101012120linear algebra notation for quantum circuits101000111010101001corresponds tocorresponds tocorresponds to2i21212icorresponds tocorres

11、ponds toie001linear algebra notation for quantum circuits0corresponds to012i21212iie0012i21212ilinear algebra notation for quantum circuitsi1001uuuuuuuuuu*11100100t11*01100011100100uuuuuis unitary if and only ifwhat is unitary matrix?abstractionthe two position states of a photon in a mach-zehnder a

12、pparatus is just one example of a quantum bit or qubitexcept when addressing a particular physical implementation, we will simply talk about “basis” states and and unitary operations likeand01hqubits as binary quditsin multi-valued (mv) quantum computing (qc), the unit of memory (information) is qud

13、it. for instance, ternary logic values of 0, 1, and 2 are represented by a set of distinguishable different basis states of a qutrit. these states can be a photons polarizations or an elementary particles spins. after encoding these distinguishable quantities into multiple-valued values, qutrit stat

14、es are represented by basis states |0, |1 and |2 , respectively. a qubit, used in binary qc uses only two basis states, |0 and |1qubit and qutrit are then special cases of qudits abap bq ccabr h-21212121im+-re21212121|0|1+-2121register-transfer notation for quantum circuits|0|0|1|11010ie001ie|0|1-+c

15、os sin cos sin register-transfer notation for quantum circuitsan arrangement like0is represented with a network likehh0h0h+-21212121+-+- 21212121+-+cos -sin cos sin superposition property may be mathematically described using the kronecker product (tensor product) operation the kronecker product of

16、two matrices is defined as follows:dvdzcvczdydxcycxbvbzavazbybxayaxvzyxdvzyxcvzyxbvzyxavzyxdcbakronecker product of matrices(b)h(a)h+- 21212121+-+- 21212121+-+- 21212121+-+- 21212121+-|0|0|1|1|00|01|10|11|0|1|00|01|10|11|0|1quantum parallelism put all 7-bits into a superposition state superposition

17、allows quantum computer to make calculations on all 128 possible numbers (27) in one iteration i.e. finishes in 1 second. tremendous possibilities imagine doing computations on even larger sample spaces all at the same time! 1010if we concatenate two qubits11100100110110001010we have a 2-qubit syste

18、m with 4 basis states0000011010011111and we can also describe the state asor by the vector10101101000in general we can have arbitrary superpositions11011000111001001211210201200where there is no factorization into the tensor product of two independent qubits.these states are called entangled.measuri

19、ng multi-qubit systemsif we measure both bits ofwe getwith probability 1101100011100100yx2xyclassical versus quantum goal: fast, low-cost implementation of useful algorithms using standard components (gates) and design techniques classical logic circuits circuit behavior is governed implicitly by cl

20、assical physics signal states are simple bit vectors, e.g. x = 01010111 operations are defined by boolean algebra no restrictions exist on copying or measuring signals small well-defined sets of universal gate types, e.g. nand,and,or,not, and,not, etc. well developed cad methodologies exist circuits

21、 are easily implemented in fast, scalable and macroscopic technologies such as cmosclassical vs. quantum circuitsquantum measurement measurement yields only one state x of the superposed states measurement also makes x the new state and so interferes with computational processes x is determined with

22、 some probability, implying uncertainty in the result states cannot be copied (“cloned”), implying that signal fanout is not permitted environmental interference can cause a measurement-like state collapse (decoherence) quantum circuits are differentdecoherence quantum logic circuits circuit behavio

23、r is governed explicitly by quantum mechanics signal states are vectors interpreted as a superposition of binary “qubit” vectors with complex-number coefficients operations are defined by linear algebra over hilbert space and can be represented by unitary matrices with complex elements severe restri

24、ctions exist on copying and measuring signals many universal gate sets exist but the best types are not obvious circuits must use microscopic technologies that are slow, fragile, and not yet scalable, e.g., nmrclassical versus quantum circuits ciin -1in-1i0i02n-1unitary operations gates and circuits

25、 must be reversible (information-lossless) number of output signal lines = number of input signal lines the circuit function must be a bijection, implying that output vectors are a permutation of the input vectors classical logic behavior can be represented by permutation matrices non-classical logi

26、c behavior can be represented including state sign (phase) and entanglementmore quantum circuit characteristicsclassical vs. quantum circuitsclassical addercn1s0s1s2s3cna0b0a1b1a3b3a2b2sumcarryclassical vs. quantum circuitsquantum adderfeynman gatereversible circuitsreversible circuits reversibility

27、 was studied around 1980 motivated by power minimization considerations bennett, toffoli et al. showed that any classical logic circuit c can be made reversible with modest overheadn inputsgenericbooleancircuitm outputsf(i)ireversible booleancircuitf(i)“junk”i“junk” how to make a given f reversible

28、suppose f :i f(i) has n inputs m outputs introduce n extra outputs and m extra inputs replace f by frev: i, j i, f(i) j where is xor example 1: f(a,b) = and(a,b) this is the well-known toffoli gate, which realizes and when c = 0, and nand when c = 1.reversible circuitsreversibleandgateabf = ab cabca

29、 b c a b f0 0 0 0 0 00 0 1 0 0 10 1 0 0 1 00 1 1 0 1 11 0 0 1 0 01 0 1 1 0 11 1 0 1 1 11 1 1 1 1 0 reversible gate family toffoli 1980reversible circuits(toffoli gate) every boolean function has a reversible implementation using toffoli gates. there is no universal reversible gate with fewer than th

30、ree inputs quantum gates input state: c0|0 + c1|1 output state: c1|0 + c0|1 pure states are mapped thus: |0 |1 and |1 |0 gate operator (matrix) is as expected:011001101001notnotnot01100 101 01one-input gate: “square root of not” some matrix elements are imaginary gate operator (matrix): we find: so

31、|0 |0 with probability |i/2|2 = 1/2 and |0 |1 with probability |1/ 2|2 = 1/2 similarly, this gate randomizes input |1 but concatenation of two gates eliminates the randomness!i/1/21/1/21/ 1/2i/ 1/ 212i11i12i11i1012i112i11ii11i0ii0notnotquantum gates one-input gate: hadamard maps |0 1/ 2 |0 + 1/ 2 |1

32、 and |1 1/ 2 |0 1/ 2 |1. ignoring the normalization factor 1/ 2, we can write | (-1) | |1 one-input gate: phase shift12111-1h100ei requirement: hadamard and phase-shift gates form a universal gate set example: the following circuit generates |y = cos |0 + ei sin |1 up to a global factoruniversal one

33、-input quantum gate setsu|0any state|y2hh2quantum xor gate called also feynman gate or controlled not gate. this gate allows inputs of |00 and |01 to appear unchanged at the outputs, but interchanges the pairs |10 and |11. for example, consider the quantum xor gates operation for an input |10.100001

34、000100100000100001|00|00|01|01|10|10|11|11|x|y|x|x y cnot1000010000010010 cnot maps |x|0 |x|xand |x|1 |x|not x |x|0 |x|x looks like cloning, but its not. these mappings are valid only for the pure states |0 and |1|x|y|x|x yquantum xor gate1000000001000000001000000001000000001000000001000000000100000

35、010|b|c|b|ab c|a|a|000|000|001|001|110|010|111|011|010|011|100|101|100|101|110|111 general controlled gates that control some 1-qubit unitary operation u are usefuluu00u01u10u11c(u)uc2(u)uuetc.universal gate sets to implement any unitary operation on n qubits exactly requires an infinite number of g

36、ate types the (infinite) set of all 2-input gates is universal any n-qubit unitary operation can be implemented using (n34n) gates reck et al. 1994 cnot and the (infinite) set of all 1-qubit gates is universalquantum gatesdiscrete universal gate sets the error on implementing u by v is defined as if

37、 u can be implemented by k gates, we can simulate u with a total error less than with a gate overhead that is polynomial in log(k/) a discrete set of gate types g is universal, if we can approximate any u to within any 0 using a sequence of gates from g quantum gatese(u,v) max(u - v)discrete univers

38、al gate set example 1: four-member “standard” gate setquantum gates100001000001001012111-1h100is/8100ei/4 cnot hadamard phase /8 (t) gate example 2: cnot, hadamard, phase, toffoli quantum circuits a quantum (combinational) circuit is a sequence of quantum gates, linked by “wires” the circuit has fix

39、ed “width” corresponding to the number of qubits being processed logic design (classical and quantum) attempts to find circuit structures for needed operations that are functionally correct independent of physical technology low-cost, e.g., use the minimum number of qubits or gates quantum logic des

40、ign is not well developed!quantum circuits ad hoc designs known for many specific functions and gates example 1 illustrating a theorem by barenco et al. 1995: any c2(u) gate can be built from cnots, c(v), and c(v) gates, where v2 = uquantum circuitsvvv=u|0|1|x|0 |1 |x |0|1|xvvv=u|0|1v|x|0|1|0|1|x|0|

41、1|0|1|x?|1|1|x|1|1|x|1|1u|xvvv=u|1|1v|x|1|0|1|0v|x|1|1|1|1u|xsimulation continued?algebraic analysis of quantum circuitsu4u2u3u1u5u0vvv=u?x1x2x3 is u0(x1, x2, x3) = u5u4u3u2u1(x1, x2, x3) = (x1, x2, x1x2 u (x3) ) ?quantum circuitsexample 1 (contd);u1 i1c(v)10011000010000v00v0100v10v11100000000100000

42、000v00v01000000v10v1100000000100000000100000000v00v01000000v10v11quantum circuitsexample 1 (contd);u2 u4 cnot(x1,x2) i1100001000001001010011000000001000000001000000001000000000010000000010000100000000100quantum circuitsexample 1 (contd); u5 is the same as u1 but has x1and x2 permuted (tricky!) it re

43、mains to evaluate the product of five 8 x 8 matrices u5u4u3u2u1 using the fact that vv = i and vv = u100000000100000000100000000100000000v00v01000000v10v1100000000v00v01000000v10v111000000001000000001000000001000000000010000000010000100000000100100000000100000000v00v10000000v01v110000000010000000010

44、0000000v00v10000000v01v111000000001000000001000000001000000000010000000010000100000000100100000000100000000v00v01000000v10v1100000000100000000100000000v00v01000000v10v11100000000100000000100000000100000000100000000100000000v00v00 v10v10v00v01 v10v11000000v01 v00 v11v10v01v01 v11v11 u0quantum circuit

45、s implementing a half adder problem: implement the classical functions sum = x1 x0 and carry = x1x0 generic design:|x1uadd|x0|y1|y0|x1|x0|y1 carry|y0 sumquantum circuits half adder: generic design (contd.)uadd1000000000000000010000000000000000100000000000000001000000000000000001000000000000001000000

46、000000000000100000000000000100000000000000000010000000000000010000000000000000001000000000000001000000000000000000010000000000000000100000000000100000000000000001000quantum circuits half adder: specific (reduced) design|x1|x0|y|x1|y carrysum c2not (toffoli)cnotwalsh transform for two binary-input ma

47、ny-valued variables+-+-+-+-you need a butterflyhclassical logicquantum logichbutterfly is created automatically by tensor product corresponding to superpositionmintermsvariable 1variable 1 tremendous potential for truly innovative researchresearch potential our community should develop a systematic

48、methodology and cad tools for synthesizing, verifying, testing and simulating of quantum computers. these methods and tools will be counterparts of what exists now in binary cmos. re-use spectral approaches, dds, xor logic, etc. development of these tools will require understanding of real quantum c

49、ircuit technology.new frontiersquantum computerquantum mechanicsquantum logicquantum computersquantum programmingopen problems in quantum circuitssynthesis of binary quantum cascades with no garbage or small garbage (maslov, dueck, miller, kerntopf, perkowski, khlopotine, mishchenko, curtis, khan, j

50、ha and agrawal, hayes, markov)synthesis of multiple-valued quantum cascades (muthukrishnan and stroud, miller et al, khan, perkowski, curtis, lee, denler) universal gates, what are the counterparts of toffoli and fredkin gates?fredkintoffoliopen problems in quantum circuits what is the fault model f

51、or quantum circuits? technology dependent? formal verification of quantum circuits test generation for quantum circuits fault localization of quantum circuits synthesis of testable quantum circuits synthesis of fault-tolerant, error correcting quantum circuits.open problems in quantum circuits what

52、are universal gates? how to calculate costs of elementary gates for each quantum technology such as nmr or ion trap? what are the gates that can be truly realized in a quantum technology? what are the synthesis, analysis and test methods for sequential quantum circuits?open problems in quantum circu

53、its invent new quantum algorithms. what are the principles to create quantum algorithms the nature of entanglement. quantum computer architectures. quantum formalisms. (clifford algebras). quantum logic. analogous to binary quantum circuits. as an example, consider two qutrits. when the two qutrits

54、are considered to represent a state, that state is the superposition of all possible combinations of the original qutrits, where:2221201211100201002121212121212121212112yyymv tensor productsthis approach to multi-valued quantum circuits requires measurements with more than two basis states. also, ne

55、w gates should be defined as well as the synthesis methods for these gates.quantum mv superposition the superposition property allows the qubit states to grow much faster in dimension than classical bits, and the qudits faster than qubits. in a classical system, n bits represent distinct states, whe

56、reas n qubits correspond to a superposition of 2n states and n qutrits correspond to a superposition of 3n states. because in contemporary quantum technologies every qubit is costly, higher radices than 2 give an advantage of improved processing and storage power at the same realization cost. this i

57、s a strong argument for realization of multi-valued logic in quantum circuits. in addition to standard advantages of mv logic, quantum mv logic may be superior to binary one because of different nature of entanglement.bloch spherethe normalization |2 + |2 = 1 admits the parametrization = cos(/2) e j

58、 , = sin(/2) e j. | = e j (cos ( / 2) |0 + e j sin ( / 2) |1 ). since the global phase of | has no observable effect, we may write | = cos( /2) |0 + e j sin( /2) |1 . the angles and define a point on the surface of a unit sphere the bloch sphere, see fig. 1. the bloch sphere provides an excellent to

59、ol to visualize the state vector of a qubit. this is a binary bloch sphere, but a multi-valued counterpart of it can be also created. second method to realize multi-valued logic using binary quantum computing (cont). figure shows the location of 6 points, that may correspond to values of some multi-

60、valued algebras. for binary logic we use |0 and |1. for quaternary logic we use |0, |1, |0+|1, and |0-|1. for 6-valued logic we may use additionally |0 + j |1 and |0 - j|1. a rotation or a combination of rotations leads from one value to any other value. second method to realize mv quantum circuits