Transcription
Quantum computing for dummiesCarlos CotriniETH Zürichccarlos@inf.ethz.chSeptember 14, 2019Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20191 / 48
What is quantum computing?From Wikipedia: “Quantum computing is the use of quantum-mechanicalphenomena such as superposition and entanglement to performcomputation.”It can, in some cases, be much more faster than classical computing.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20192 / 48
A toy problemA bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20193 / 48
A toy problemA bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.The problemGiven a bit array f of length 2n , known to be balanced or constant, decideif it is balanced.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20193 / 48
A toy problemA bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.The problemGiven a bit array f of length 2n , known to be balanced or constant, decideif it is balanced.A classical computer takes time linear in the length of the bit array tosolve this problem.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20193 / 48
A toy problemA bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.The problemGiven a bit array f of length 2n , known to be balanced or constant, decideif it is balanced.A classical computer takes time linear in the length of the bit array tosolve this problem.A quantum computer takes logarithmic time (by the Deutsch-Jozsaalgorithm).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20193 / 48
A more practical exampleA quantumcomputer can find an element in an array of length N in O( N)-time (by Grover’s algorithm).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20194 / 48
Overview1BackgroundQubits and qubit arraysQuantum gates2The Deutsch-Jozsa algorithm3Grover’s algorithmBackground in linear algebraGrover’s algorithmCarlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20195 / 48
QubitsAssume I have a closed box with a cat inside.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20196 / 48
QubitsAssume I have a closed box with a cat inside.If it is a classical cat, then it is either dead or alive.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20196 / 48
QubitsAssume I have a closed box with a cat inside.If it is a classical cat, then it is either dead or alive.If it is a quantum cat, then it is both dead and alive. A quantumphenomenon called superposition.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20196 / 48
QubitsAssume I have a closed box with a cat inside.If it is a classical cat, then it is either dead or alive.If it is a quantum cat, then it is both dead and alive. A quantumphenomenon called superposition.A bit is a value that is either 0 or 1.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20196 / 48
QubitsAssume I have a closed box with a cat inside.If it is a classical cat, then it is either dead or alive.If it is a quantum cat, then it is both dead and alive. A quantumphenomenon called superposition.A bit is a value that is either 0 or 1.A quantum bit is a value that is both 0 and 1 (superposition).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20196 / 48
QubitsWhat is a qubit?Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )Carlos Cotrini (ETH Zürich)P(0)P(1)1212QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )( 12 , 12 )Carlos Cotrini (ETH Zürich)P(0)P(1)1212QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )( 12 , 12 )Carlos Cotrini (ETH Zürich)P(0)P(1)12121212QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )( 12 , 12 )(0, 1)Carlos Cotrini (ETH Zürich)P(0)P(1)12121212QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )( 12 , 12 )(0, 1)Carlos Cotrini (ETH Zürich)P(0)P(1)1212121201QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )( 12 , 12 )(0, 1)( 1, 0)Carlos Cotrini (ETH Zürich)P(0)P(1)1212121201QC for dummiesSeptember 14, 20197 / 48
QubitsWhat is a qubit?(a0 , a1 ) C2 with a0 2 a1 2 1. a0 2 probability that we get a 0, when we measure the qubit. a1 2 probability that we get a 1, when we measure the qubit.Examples:Qubits( 12 , 12 )( 12 , 12 )(0, 1)( 1, 0)Carlos Cotrini (ETH Zürich)P(0)P(1)121212120110QC for dummiesSeptember 14, 20197 / 48
QubitsValueStateProbability07 a07 a0 217 a17 a1 2Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20198 / 48
A qubit represents a single storage unit where both a 0 and a 1 are storedat the same time (in superposition). It is not that a qubit is storing twovalues in “physically” different spaces. The 0 and the 1 are in the same“physical” space.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 20199 / 48
Qubit arraysCarlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201910 / 48
Qubit arraysFix n N.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201910 / 48
Qubit arraysFix n N.A bit array is one sequence of n bits.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201910 / 48
Qubit arraysFix n N.A bit array is one sequence of n bits.A qubit array is all sequences of n bits (superposition).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201910 / 48
Qubit arraysFix n N.A bit array is one sequence of n bits.A qubit array is all sequences of n bits (superposition).When you observe the array, you see a bit array x of n bits with probability ax 2 .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201910 / 48
Qubit arraysFix n N.A bit array is one sequence of n bits.A qubit array is all sequences of n bits (superposition).When you observe the array, you see a bit array x of n bits with probability ax 2 .So a qubit array is defined by one complex number ax for each possible bitarray in {0, 1}n .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201910 / 48
Qubit arraysCarlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.xCarlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit arrayCarlos Cotrini (ETH Zürich)P(00)P(01)QC for dummiesP(10)P(11)September 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit array(0, 12 , 0, 12 )Carlos Cotrini (ETH Zürich)P(00)P(01)QC for dummiesP(10)P(11)September 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit array(0, 12 , 0, 12 )Carlos Cotrini (ETH Zürich)P(00)0P(01)12QC for dummiesP(10)0P(11)12September 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit array(0, 12 , 0, 12 )(0, 12 , 12 , 12 )Carlos Cotrini (ETH Zürich)P(00)0P(01)12QC for dummiesP(10)0P(11)12September 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit array(0, 12 , 0, 12 )(0, 12 , 12 , 12 )Carlos Cotrini (ETH Zürich)P(00)00P(01)1212QC for dummiesP(10)014P(11)1214September 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit array(0, 12 , 0, 12 )(0, 12 , 12 , 12 )(1, 0, 0, 0)Carlos Cotrini (ETH Zürich)P(00)00P(01)1212QC for dummiesP(10)014P(11)1214September 14, 201911 / 48
Qubit arraysWhat is a qubit array of length n?(a0 , a1 , . . . , aN 1 ) CN , with N 2n andXsuch that ax 2 1.x ax 2 is the probability, that after observing the qubit array, we get x.Examples:Qubit array(0, 12 , 0, 12 )(0, 12 , 12 , 12 )(1, 0, 0, 0)Carlos Cotrini (ETH Zürich)P(00)001P(01)12120QC for dummiesP(10)0P(11)14121400September 14, 201911 / 48
Qubit arraysMore examples: (1/2, 0, 0, 1/2, 0, 0, 0, 1/ 2) is a qubit array that, when observed,yields 000 with prob 1/4, 011 with prob 1/4, and 111 with probability1/2.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201912 / 48
Qubit arraysMore examples: (1/2, 0, 0, 1/2, 0, 0, 0, 1/ 2) is a qubit array that, when observed,yields 000 with prob 1/4, 011 with prob 1/4, and 111 with probability1/2. (1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8, 1/ 8) is a qubit arraythat, when observed, yields any bit array of length 3 with equalprobability.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201912 / 48
Qubit arrays000001010011100101110111Carlos Cotrini (ETH Zürich)7 7 7 7 7 7 7 7 a000a001a010a011a100a101a110a1117 7 7 7 7 7 7 7 a0a1a2a3a4a5a6a7QC for dummies7 7 7 7 7 7 7 7 a0 2 a1 2 a2 2 a3 2 a4 2 a5 2 a6 2 a7 2September 14, 201913 / 48
A qubit array of length n is a storage unit with n bits of capacity. A qubitarray is not a data structure containing all bit arrays in 2n “physically”different locations. All 2n bit arrays are in the “physical” storage unit withn bits of capacity, coexisting in superposition.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201914 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Examples:Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Examples: 10i (0, 0, 1, 0).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Examples: 10i (0, 0, 1, 0). 011i (0, 0, 0, 1, 0, 0, 0, 0).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Examples: 10i (0, 0, 1, 0). 011i (0, 0, 0, 1, 0, 0, 0, 0). 0000i (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0).Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Examples: 10i (0, 0, 1, 0). 011i (0, 0, 0, 1, 0, 0, 0, 0). 0000i (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0).DefinitionBn : { xi x {0, 1}n } .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Qubit arrays are vectors in CNFor x {0, 1}n , let xi be the qubit array with all entries equal zero exceptthe x-th, which is 1.Examples: 10i (0, 0, 1, 0). 011i (0, 0, 0, 1, 0, 0, 0, 0). 0000i (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0).DefinitionBn : { xi x {0, 1}n } .Example: B2 { 00i , 01i , 10i , 11i}.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201915 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nCarlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201916 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nPx {0,1}nax xi is ψi’s algebraic representation.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201916 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nPx {0,1}nax xi is ψi’s algebraic representation.(a0 , a1 , . . . , aN ) is ψi’s vector representation.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201916 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nPx {0,1}nax xi is ψi’s algebraic representation.(a0 , a1 , . . . , aN ) is ψi’s vector representation.Examples:Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201916 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nPx {0,1}nax xi is ψi’s algebraic representation.(a0 , a1 , . . . , aN ) is ψi’s vector representation.Examples: 1 , 1 22Carlos Cotrini (ETH Zürich) 1 (1, 0)2 1 (0, 1)2 QC for dummies 12 0i 12 1i .September 14, 201916 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nPx {0,1}nax xi is ψi’s algebraic representation.(a0 , a1 , . . . , aN ) is ψi’s vector representation.Examples: 1 , 1 12 (1, 0) 12 (0, 1) 12 0i 12 1i .22 0, 12 , 12 , 0 12 (0, 1, 0, 0) 12 (0, 0, 1, 0) 12 01i Carlos Cotrini (ETH Zürich)QC for dummies 12September 14, 2019 10i .16 / 48
Bn is a basisLet ψi (a0 , a1 , . . . , aN 1 ), then ψi Xax xi .x {0,1}nPx {0,1}nax xi is ψi’s algebraic representation.(a0 , a1 , . . . , aN ) is ψi’s vector representation.Examples: 1 , 1 12 (1, 0) 12 (0, 1) 12 0i 12 1i .22 0, 12 , 12 , 0 12 (0, 1, 0, 0) 12 (0, 0, 1, 0) 12 01i 12 10i .(0, 0, 0, 0, 0, 0, 0, 1) (0, 0, 0, 0, 0, 0, 0, 1) 111i .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201916 / 48
MeasurementsA measurement operator receives as input a qubit arrayoutputs x with probability ax 2 .Carlos Cotrini (ETH Zürich)QC for dummiesPxax xi andSeptember 14, 201917 / 48
MeasurementsA measurement operator receives as input a qubit arrayoutputs x with probability ax 2 .Examples:Measuring 12 0i Carlos Cotrini (ETH Zürich) 32Pxax xi and 1i yields 1 with probability 34 .QC for dummiesSeptember 14, 201917 / 48
MeasurementsA measurement operator receives as input a qubit arrayoutputs x with probability ax 2 .Examples:Measuring 12 0i 32Pxax xi and 1i yields 1 with probability 34 .Measuring 1i yields 1 with probability 1.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201917 / 48
MeasurementsA measurement operator receives as input a qubit arrayoutputs x with probability ax 2 .Examples:Measuring 12 0i 32Pxax xi and 1i yields 1 with probability 34 .Measuring 1i yields 1 with probability 1.ObservationAfter measuring a qubit array, all its uncertainty is lost. Measuring againgives the same result.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201917 / 48
Quantum gatesA quantum gate is a unitary transformation G : CN CN .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201918 / 48
Quantum gatesA quantum gate is a unitary transformation G : CN CN .For now, the most important thing to know about unitary transformationsis that they are linear:!XXGax xi ax G xi .xCarlos Cotrini (ETH Zürich)xQC for dummiesSeptember 14, 201918 / 48
Quantum gatesA quantum gate is a unitary transformation G : CN CN .For now, the most important thing to know about unitary transformationsis that they are linear:!XXGax xi ax G xi .xxExample: 111111G 00i 10i 11i G 00i G 10i G 11i .222222Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201918 / 48
Quantum gatesA quantum gate is a unitary transformation G : CN CN .For now, the most important thing to know about unitary transformationsis that they are linear:!XXGax xi ax G xi .xxExample: 111111G 00i 10i 11i G 00i G 10i G 11i .222222To compute G ψi, you only need to know how G works on Bn .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201918 / 48
Popular quantum gatesHadamard gate.Emulation gate.Reflection gate.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201919 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi nCarlos Cotrini (ETH Zürich)( 1)x 2n y i ,x[i]y [i] is the classical inner product.QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yXH xi : y {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:H 0i Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:11H 0i 0i 1i .22Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:11H 0i 0i 1i .22H 01i Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:11H 0i 0i 1i .22H 01i Carlos Cotrini (ETH Zürich)1 00i2QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:11H 0i 0i 1i .22H 01i Carlos Cotrini (ETH Zürich)11 00i 01i22QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:11H 0i 0i 1i .22H 01i Carlos Cotrini (ETH Zürich)111 00i 01i 10i222QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gateFor xi Bn , yH xi : Xy {0,1}nwhere x y : Pi n( 1)x 2n y i ,x[i]y [i] is the classical inner product.Example:11H 0i 0i 1i .22H 01i Carlos Cotrini (ETH Zürich)1111 00i 01i 10i 11i .2222QC for dummiesSeptember 14, 201920 / 48
Quantum gate example: Hadamard gate yXH xi : y {0,1}n( 1)x 2n y i ,In particular,H 00 . . . 0i Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201921 / 48
Quantum gate example: Hadamard gate yXH xi : y {0,1}n( 1)x 2n y i ,In particular,H 00 . . . 0i Xy {0,1}nCarlos Cotrini (ETH Zürich)1 y i : ?i .2nQC for dummiesSeptember 14, 201921 / 48
Quantum gate example: Hadamard gateIn general, for any qubit array ψi H ψi HXPxax xi,!ax xixCarlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201922 / 48
Quantum gate example: Hadamard gateIn general, for any qubit array ψi H ψi HXPxax xi,!ax xix Xax H xixX ax ( 1)x y y i2nx,yX X ax ( 1)x y 2nyx! y i .Applying the Hadamard gate takes constant time! It is not that the gatecomputes H xi, for each x! Remember that all bit arrays x are insuperposition!Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201922 / 48
Quantum gate example: Emulation gateIf f : {0, 1}n {0, 1} is a Boolean circuit, thenUf xi : ( 1)f (x) xi .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201923 / 48
Quantum gate example: Emulation gateIf f : {0, 1}n {0, 1} is a Boolean circuit, thenUf xi : ( 1)f (x) xi .In general, for any qubit array ψi,!Uf ψi UfXax xi xCarlos Cotrini (ETH Zürich)Xax ( 1)f (x) xi .xQC for dummiesSeptember 14, 201923 / 48
Quantum gate example: Emulation gateIf f : {0, 1}n {0, 1} is a Boolean circuit, thenUf xi : ( 1)f (x) xi .In general, for any qubit array ψi,!Uf ψi UfXax xi xXax ( 1)f (x) xi .xIf computing f (x) takes O(K )-time, then computing Uf ψi also takesO(K )-time.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201923 / 48
Quantum gate example: Reflection gate( 00 . . . 0iF xi xiCarlos Cotrini (ETH Zürich)if x 00 . . . 0 andotherwise.QC for dummiesSeptember 14, 201924 / 48
Classical vs parallel vs quantum computationf : {0, 1}n {0, 1}. Suppose that computing f (x) takes O(K (n))-time.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201925 / 48
Classical vs parallel vs quantum computationf : {0, 1}n {0, 1}. Suppose that computing f (x) takes O(K (n))-time.How much you need to compute f ’s table?Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201925 / 48
Classical vs parallel vs quantum computationf : {0, 1}n {0, 1}. Suppose that computing f (x) takes O(K (n))-time.How much you need to compute f ’s table?ClassicalCarlos Cotrini (ETH Zürich)MemoryO(2n )TimeO(2n K (n))QC for dummiesEnergyO(2n K (n))September 14, 201925 / 48
Classical vs parallel vs quantum computationf : {0, 1}n {0, 1}. Suppose that computing f (x) takes O(K (n))-time.How much you need to compute f ’s table?ClassicalParallel (2n cores)Carlos Cotrini (ETH Zürich)MemoryO(2n )O(2n )TimeO(2n K (n))O(K (n))QC for dummiesEnergyO(2n K (n))O(2n K (n))September 14, 201925 / 48
Classical vs parallel vs quantum computationf : {0, 1}n {0, 1}. Suppose that computing f (x) takes O(K (n))-time.How much you need to compute f ’s table?ClassicalParallel (2n cores)QuantumCarlos Cotrini (ETH Zürich)MemoryO(2n )O(2n )O(n)TimeO(2n K (n))O(K (n))O(K (n))QC for dummiesEnergyO(2n K (n))O(2n K (n))O(K (n))September 14, 201925 / 48
Classical vs parallel vs quantum computationf : {0, 1}n {0, 1}. Suppose that computing f (x) takes O(K (n))-time.How much you need to compute f ’s table?ClassicalParallel (2n cores)QuantumMemoryO(2n )O(2n )O(n)TimeO(2n K (n))O(K (n))O(K (n))EnergyO(2n K (n))O(2n K (n))O(K (n))* Constants may vary substantially.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201925 / 48
Quantum computing for dummiesCarlos CotriniETH Zürichccarlos@inf.ethz.chSeptember 14, 2019Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201926 / 48
The Deutsch-Jozsa algorithmAnd now. a problem that can be solved in linear time by a classicalcomputer, but in constant time by a quantum computer!A bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201927 / 48
The Deutsch-Jozsa algorithmAnd now. a problem that can be solved in linear time by a classicalcomputer, but in constant time by a quantum computer!A bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.The problemGiven a bit array f of length 2n , known to be balanced or constant, decideif it is balanced.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201927 / 48
The Deutsch-Jozsa algorithmAnd now. a problem that can be solved in linear time by a classicalcomputer, but in constant time by a quantum computer!A bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.The problemGiven a bit array f of length 2n , known to be balanced or constant, decideif it is balanced.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201927 / 48
The Deutsch-Jozsa algorithmAnd now. a problem that can be solved in linear time by a classicalcomputer, but in constant time by a quantum computer!A bit array of length 2n is balanced if exactly half of its entries are zero. Abit array is constant if all its entries are zero.The problemGiven a bit array f of length 2n , known to be balanced or constant, decideif it is balanced.Executing this circuit requires only just one call to Uf .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201927 / 48
ExercisesObserve that 0i 00.0i. Recall that yXH xi : y {0,1}n( 1)x 2nUf xi : ( 1)f (x) xi . y i .We now show why this circuit decides if f is balanced or constant.Show that ψ 0 HUf H 00 . . . 0i Xz y f (y )X z {0,1}ny {0,1}n( 1) 2n zi .After we measure ψ 0 i, what is the probability that we get 00 . . . 0 if fis balanced? What is the probability of getting 00 . . . 0 if f isconstant?Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201928 / 48
Agenda1Background in linear algebra.Linear transformations.Matrix representations.Unitary transformations.2Grover’s algorithm.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201929 / 48
Searching with a quantum computerThe problemGiven a function f : {0, 1}n {0, 1}, find an element x {0, 1}n suchthat f (x) 1. We call such an element a solution of f .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201930 / 48
Searching with a quantum computerThe problemGiven a function f : {0, 1}n {0, 1}, find an element x {0, 1}n suchthat f (x) 1. We call such an element a solution of f .A classical computer solves this in O(2n )-time.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201930 / 48
Searching with a quantum computerThe problemGiven a function f : {0, 1}n {0, 1}, find an element x {0, 1}n suchthat f (x) 1. We call such an element a solution of f .A classical computer solves this in O(2n )-time. A quantum computer can solve this in O( 2n )-time!Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201930 / 48
Searching with a quantum computerThe problemGiven a function f : {0, 1}n {0, 1}, find an element x {0, 1}n suchthat f (x) 1. We call such an element a solution of f .A classical computer solves this in O(2n )-time. A quantum computer can solve this in O( 2n )-time!We assume that there are M N 2n solutions of f .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201930 / 48
Linear transformationsA linear transformation is a function T : CN CN such thatT (a1 ψ1 i a2 ψ2 i) a1 T ψ1 i a2 T ψ2 i .Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201931 / 48
Linear transformationsA linear transformation is a function T : CN CN such thatT (a1 ψ1 i a2 ψ2 i) a1 T ψ1 i a2 T ψ2 i .Every linear transformation T is identified with a unique matrixJT K CN N such that T ψi JT K ψi. We identify T with JT K.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201931 / 48
How to compute the matrix representation of a lineartransformation T ?1List all basic qubit arrays: 00 . . . 0i , 00 . . . 1i , . . . , 11 . . . 1i.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201932 / 48
How to compute the matrix representation of a lineartransformation T ?1List all basic qubit arrays: 00 . . . 0i , 00 . . . 1i , . . . , 11 . . . 1i.2Apply T to each of them: T 00 . . . 0i , T 00 . . . 1i , . . . , T 11 . . . 1i.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201932 / 48
How to compute the matrix representation of a lineartransformation T ?1List all basic qubit arrays: 00 . . . 0i , 00 . . . 1i , . . . , 11 . . . 1i.2Apply T to each of them: T 00 . . . 0i , T 00 . . . 1i , . . . , T 11 . . . 1i.3Write these qubit arrays as column vectors.Carlos Cotrini (ETH Zürich)QC for dummiesSeptember 14, 201932 / 48
How to compute the matrix representation of a lineartransformation T ?1List all basic qubit arrays: 00 . . . 0i ,
Quantum computing for dummies Carlos Cotrini ETH Zurich ccarlos@inf.ethz.ch September 14, 2019 Carlos Cotr
