## Canadian Summer School on Quantum Information (CSSQI) (10th : 2010)

Media
59370-AQC Amin 1.mp4 [ 219.36MB ]
59370-AQC Amin 2.mp4 [ 203.82MB ]
59370-quantum_computation1.pdf [ 155.2kB ]
59370-quantum_computation2.pdf [ 453.89kB ]
59370-quantum_computation3.pdf [ 380.03kB ]
59370-quantum_computation4.pdf [ 1.1MB ]
JSON: 59370-1.0040933.json
JSON-LD: 59370-1.0040933-ld.json
RDF/XML (Pretty): 59370-1.0040933-rdf.xml
RDF/JSON: 59370-1.0040933-rdf.json
Turtle: 59370-1.0040933-turtle.txt
N-Triples: 59370-1.0040933-rdf-ntriples.txt
Original Record: 59370-1.0040933-source.json
Full Text
59370-1.0040933-fulltext.txt
Citation
59370-1.0040933.ris

#### Full Text

`Introduction to Adiabatic Quantum Computation Mohammad Amin D-Wave System Inc.  Topics: 1. Introduction to AQC 2. Effect of noise on AQC 3. Quantum annealing and quantum phase transition 4. Quantum annealing with superconducting qubits  •2•  Quantum Evolution Schrödinger equation:  ih  dψ dt  =Hψ  Planck constant  Time evolution operator: For time-independent H:  •3•  Hamiltonian  ψ (t ) = U (t ) ψ (0)  U (t ) = e  − iHt / h  Quantum Gates ψ  Uψ H  0  δt t  Hamiltonian is applied only at the time of gate operation  •4•  Eigenstates and Eigenvalues: H ψ n = En ψ n Eigenstate  Eigenvalue  Question: What happens if the system starts in an eigenstate?  ψ (0) = ψ n ψ n (t ) = e −iHt / h ψ n = e − iE t / h ψ n n  Answer: Nothing! The system will stay in the same eigenstate •5•  Adiabatic Quantum Computation (AQC) E. Farhi et al., Science 292, 472 (2001)  E . . .  System Hamiltonian:  H = (1− λ) HB + λ HP  gm  . . .  E1 E0 0  • Prepare the system in the ground state of HB • Slowly vary λ(t) from 0 to 1 • Read out the final state which is ground state of HP •6•  1  λ  Computation Time Energy-time uncertainty relation:  δt ⋅ δE > h  Planck constant  Uncertainty of energy (superposition in energy basis) Time spent on the energy level  •7•  Computation Time  E  Energy-time uncertainty relation:  Ef  δt ⋅ δE > h δE < g m  h ⇒ δt > gm  Uniform time sweep:  Non-uniform time sweep: •8•  δt  tf  t  Minimum gap  δt  gm = tf Ef  ⇒ tf >  hE f g m2  h t f ~ δt ⇒ t f > Optimal gm  Landau-Zener Problem  P1  E  2-State Hamiltonian:  1 H = − ( g mσ x +νtσ z ) 2  P0 0  P1 (t = −∞) = 0 ⇒ P1 (t = +∞) = e  ν= •9•  Ef tf  ⇒ P1 (t f ) ≈ e  −  π 2 g m2 hE f  tf  π 2 g m2 − hν  t  Exact solution  << 1 ⇒ t f >>  hE f g m2  Adiabatic Theorem t f >>  max λ∈[ 0,1] 0 dH / dλ 1 g m2  Controversy about adiabatic theorem: K.-P. Marzlin and B. C. Sanders, PRL 93,160408 (2004) M.S. Sarandy, L.-A. Wu, D.A. Lidar, Quant. Info. Proc. 3, 331 (2004) D. M. Tong, K. Singh, L. C. Kwek, and C. H. Oh, PRL 95, 110407 (2005) Z. Wu and H. Yang, PRA 72, 012114 (2005) S. Duki, H. Mathur, and O. Narayan, PRL 97,128901 (2006) M.H.S. Amin, PRL 102, 220401 (2009)  • 10 •  . . .  Adiabatic Theorem t f >>  max λ∈[ 0,1] 0 dH / dλ 1 g m2  Rigorous versions of adiabatic theorem: A. Ambainis, O. Regev, arXiv:quant-ph/0411152 S. Jansen, M.-B. Ruskai, and R. Seiler, J. Math. Phys. 48, 102111 (2007) D.A. Lidar, A.T. Rezakhani, and A. Hamma, J. Math. Phys 50, 102106 (2009) . . .  • 11 •  Two Types of Computation 1. Universal Adiabatic Quantum Computation D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, SIAM J. Comput. 37, 166 (2007) A. Mizel, D.A. Lidar, M. Mitchell, Phys. Rev. Lett. 99, 070502 (2007)  2. Adiabatic Quantum Optimization E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, and D. Preda, Science 292, 472 (2001)  Or Quantum Annealing A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, Chemical Physics Letters 219, 343 (1994)  • 12 •  Universal AQC Seth Lloyd, arXiv:0805.2757  Consider a quantum algorithm with n gates represented by unitary operators: U1,U2 , ... ,Un After l gates: Therefore  ψ l = U l ... U 2U1 ψ 0 ψ l +1 = U l +1 ψ l  −1 ψ = U and l −1 l ψl  Solution:  ψ n −1 = U n −1 ... U 2U1 ψ 0  Reset:  ψ n = U n ψ n −1 = ψ 0 Write down a Hamiltonian  • 13 •  with ψ n −1 being in its ground state  Pointer or Clock Qubits Define orthogonal states:  l , l = 0, ... , n  They can be represented by n additional qubits:  0 = 0...0001 1 = 0...0010 2 = 0...0100 ... n − 1 = 1...0000 n = 0 • 14 •  Hamiltonian n −1  [  H P = −∑ U l +1 ⊗ l + 1 l + U l−+11 ⊗ l l + 1 l =0  1 n −1 i 2πkl / n Ψk = e ψl ⊗ l ∑ n l =0  Define states  1 H P Ψk = − n  1 =− n  (  =−e  n −1  i 2πkl / n e ψ l +1 ∑ l =0  ∑ (e n −1  i 2πk ( l −1) / n  l =0  i 2πk / n  +e  −i 2πk / n  1 ⊗ l +1 − n  n  i 2πkl / n e ψ l −1 ⊗ l − 1 ∑ l =1  )  + ei 2πk ( l +1) / n ψ l ⊗ l  ) ∑e  = −2 cos(2πk / n ) Ψk • 15 •  ]  1 n  n −1  l =0  i 2πkl / n  ψl ⊗ l  Eigenstates of H  Ground State H P Ψk = Ek Ψk Eigenstates: Eigenvalues: Ground state: First excited state: Energy gap:  • 16 •  1 n −1 i 2πkl / n Ψk = e ψl ⊗ l ∑ n l =0  Ek = −2 cos(2π k / n) k = 0 ⇒ E0 = −2  2π k = 1 ⇒ E1 = −2 cos n 2π  2π 2  E1 − E0 = 21 − cos ≈ 2 n  n   Adiabatic Evolution H = (1 − λ ) H B + λH P Initial Hamiltonian:  H B = − l = 0 l = 0 + η (1 − ψ 0 ψ 0 ) ⊗ l = 0 l = 0 Final Hamiltonian: n −1  [  H P = −∑ U l +1 ⊗ l + 1 l + U l−+11 ⊗ l l + 1 l =0  ]  2π 2 Minimum gap happens at λ = 1, therefore g m ≈ 2 n • 17 •  Computation time ~ n4  n = # of gates  Universality AQC is computationally equivalent to gate model quantum computation They can be mapped to each other with polynomial overhead  • 18 •  Practicality n −1  [  H P = −∑ U l +1 ⊗ l + 1 l + U l−+11 ⊗ l l + 1 l =0  2-qubit interaction  =  +  ]  2-qubit interaction  4-qubit interaction  Not practical!  Using perturbation it can be reduce to 2-qubit interactions J. Kempe, A. Kitaev, and O. Regev, SIAM J. Computing 35(5), 1070 (2006)  Only XZ coupling or XX + ZZ couplings is enough J.D. Biamonte and P.J. Love, Phys. Rev. A 78, 012352 (2008)  • 19 •  Hp is not diagonal in computation basis  Adiabatic Quantum Optimization Hamiltonian:  H = (1− λ) HB + λ HP Off-diagonal (in computation basis)  Diagonal (in computation basis)  The final state is a classical state that minimizes the energy of Hp • 20 •  Adiabatic Grover Search Unstructured search problem: Find state m in a data base containing N = 2n entries with no structure  • 21 •  Classical search algorithm:  t f = O(N )  Grover search algorithm  t f = O( N )  Adiabatic Grover Search (N-2)-fold degenerate  J. Roland and N. Cerf, PRA 65, 042308 (2002)  H = (1− λ) HB + λ HP H B = 1− + +  1 + = N  H P = 1− m m  N −1  ∑  En  N = 2n  z,  1 gm = N  z =0  λ  Linear time sweep:  1 tf ~ 2 ~ N gm  Classical speed  Optimal time sweep:  1 tf ~ ~ N gm  Grover speed  • 22 •  Not practical!  Ising Problem Find a set of si = ±1 that minimizes n n r F ( s ) = ∑ hi si + ∑ J ij si s j , i =1  i , j =1  r s = [ s1 , s2 ,..., sn ]  Ising problem is NP-Hard  • 23 •  Ising Hamiltonian Find a set of si = ±1 that minimizes n n r F ( s ) = ∑ hi si + ∑ J ij si s j , i =1  i , j =1  r s = [ s1 , s2 ,..., sn ]  H = (1− λ) HB + λ HP  Hamiltonian: n  n  i =1  i , j =1  H P = ∑ hiσ iz + ∑ J ijσ izσ zj  Diagonal (in σz basis)  n  H B = −∆ ∑ σ ix i =1  • 24 •  Off-diagonal (transverse)  Open Question How does computation time scale with n? G. Rose et al., arXiv:1006.4147  • 25 •   Effect of Environment on Adiabatic Quantum Computation Mohammad Amin D-Wave Systems Inc.  Some Common Statements • Decoherence makes qubits classical bits • Quantum information is lost after decoherence time • Computation should be done within decoherence time . . .  Wrong!!! Some apply to gate model computation •2•  Open Quantum Sysytem H = H S + H env + H int System  H S ψ n = En ψ n  Interaction  Environment (Bath)  •3•  Open Quantum Sysytem H = H S + H env + H int H S ψ n = En ψ n Question:  . . .  E3 E2 E1 E0  Assume weak coupling to environment and En−E0>>T, what happens if the system starts in the ground state? Answer: System will remain in the ground state with highest probability. •4•  Open Quantum Sysytem H = H S + H env + H int H S ψ n = En ψ n  . . .  E3 E2 E1 E0  Question: Assume weak coupling to environment and En−E0>>T, what happens if the system starts in an excited state? Answer: System will relax to the ground state. •5•  Quantum Coherence H = − 12 ∆σ x  Single qubit Hamiltonian: Logical basis:  σz 0 = − 0 σz 1 = 1  0  1 Tunneling  ∆  •6•  Quantum Coherence Single qubit Hamiltonian: Eigenstates and Eigenvalues:  0  H = − 12 ∆σ x ± =  1  0 ±1 2  ,  − =  Energy gap = ∆  + = •7•  ∆ E± = m 2  0 −1 2 0 +1 2  Quantum Coherence H = − 12 ∆σ x  Single qubit Hamiltonian: Eigenstates and Eigenvalues: Initializing in state “0”:  0  •8•  ± =  0 ±1  ψ (t = 0) = 0 =  1  2  ,  + + − 2  ∆ E± = m 2  Quantum Coherence H = − 12 ∆σ x  Single qubit Hamiltonian: Eigenstates and Eigenvalues: Initializing in state “0”:  ψ (t ) =  ψ (t = 0) = 0 =  ei∆t / 2 h + + e −i∆t / 2 h − 2  1 Tunneling  ∆  2  ,  ∆ E± = m 2  + + − 2  ∆t ∆t = cos 0 + i sin 1 2h 2h  0  •9•  ± =  0 ±1  Quantum Coherence H = − 12 ∆σ x  Single qubit Hamiltonian:  Probability of finding the qubit in state “0”: P0 (t ) = 0 ψ (t )  2  1 = (1 + cos ∆t / h ) 2  0  1 Tunneling  ∆  • 10 •  Coherent Oscillations  What happens if there is an environment?  • 11 •  Open Quantum System Single qubit Hamiltonian:  H = − 12 ∆σ x + H int + H env  Eigenstates and Eigenvalues:  ± ≈  0 ±1 2  ,  ∆ E± = m + δE± 2  Uncertainty in Energy Energy-time uncertainty relation:  δt ⋅ δE > h  Relaxation time T1 • 12 •  Dephasing Time ψ (t ) ≈  Wave function: Uncertainty in phase:  + + e −i ( ∆ +δE )t / h − 2  δϕ = δE ⋅ t /h  Phase information is lost within  t ~ h / δE  Dephasing time T2  1 1 1 = + T2 2T1 Tϕ • 13 •  Pure dephasing due to classical noise  Density Matrix Approach ρ=ψ ψ  Pure state density matrix:  All information can be extracted from the density matrix:  Pa = a ψ  2  = aρa  ψ A ψ = Tr[ ρA]  Time evolution of the density matrix: Schrodinger equation  Liouville equation  i ρ& = − [ H , ρ ] h  • 14 •  Quantum mechanics can be formulated in terms of the density matrix  Pure State vs. Mixed State ψ =α 0 + β 1  Pure state density matrix:  ρ = ψ ψ = α 0 0 + αβ 0 1 + α β 1 0 + β 1 1 2  *   α 2 αβ *   = * 2 α β β     *  Nonzero off-diagonal elements represent quantum superposition  Mixed state density matrix:   P0 ρ = P0 0 0 + P1 1 1 =  0 Classical probabilities • 15 •  2  0  P1   Open Quantum System System  Bath  Interaction  Hamiltonian: Total (system + bath) density matrix:  ρ SB = ψ SB ψ SB  Reduced (system) density matrix:  ρ S = TrB [ ρ SB ]  TrB [ x] = ∑ ΨBn x ΨBn n  Environment eigenfunctions  • 16 •  Entanglement with Environment ψS =α 0 +β 1  →  ψ SB = α 0 ⊗ ψ B 0 + β 1 ⊗ ψ B1 ≈1  ≈0   α 2 TrB [ψ B 0 ψ B 0 ] αβ *TrB [ψ B 0 ψ B1 ]  ρ S = TrB [ψ SB ψ SB ] =  * 2  α β Tr [ψ ψ ] β Tr [ψ ψ ]  B B1 B0 B B1 B1   ≈1 ≈0 if ψ B 0 ψ B1 ≈ 0  α 2 ρS =   0   0  2 β   Decoherence  Entanglement with environment decoheres the qubit and generates mixed state • 17 •  Coherent Oscillations ψ (t ) =  ei∆t / 2 + + e −i∆t / 2 − 2  ∆t ∆t 0 + i sin 1 = cos 2 2  Density matrix in computation basis:   cos 2 ∆2t ρ = ψ ψ =  i  2 sin ∆t Density matrix in energy basis:  − 2i sin ∆t   2 ∆t  sin 2   12 ρ =  1 −i∆t 2e  1 2  e i∆t    1 2   Diagonal part of the density matrix does not change Off-diagonal part oscillates • 18 •  Open System Oscillations Density matrix in energy basis (weak coupling limit): Dephasing (T2) process  Relaxation (T1) process   P+eq + ( 12 − P+eq )e −t / T1 ρ =  1 −i∆t −t / T2 e 2e  eq  P →∞ → + ρ t  0  0   eq  P−    e i∆t e −t / T2  −t / T1  eq eq 1 P− + ( 2 − P− )e  1 2  − E± / T e P±eq = − E+ / T e + e − E− / T  Equilibrium (Boltzmann) Distribution  Is this a completely classical state? • 19 •  Equilibrium State Density matrix in energy basis:   P+eq ρ =   0  0   eq  P−   Density matrix in computation basis (“0” , “1”):  1 1  ρ =  eq 2  P+ − P−eq  P+eq − P−eq    1   Signature of coherent mixture  ρ is diagonal in logical basis only if P+eq = P−eq =  • 20 •  1 2  i.e.,  T >> ∆  Quantum Superposition (coherent mixture)  can persist in equilibrium  • 21 •  Coherent Tunneling Coherent oscillations  P0 (t ) = 0 ρ (t ) 0 = 12 (1 + e −γ t cos ∆t ), Decoherence rate  γ = 1 / T2 < ∆ 0  Energy gap = ∆  1 γ = broadening  Well-defined gap • 22 •  Incoherent Tunneling γ = 1 / T2 > ∆  If decoherence rate  P0 (t ) = 12 (1 + e −Γ t ),  Γ=  ∆2  γ  Incoherent tunneling rate  Incoherent tunneling is still a quantum effect  0 Energy gap = ∆  1 γ = broadening  Gap not well-defined • 23 •  Two-Qubit Example Hamiltonian:  H = − 12 ∆ (σ 1x + σ x2 ) − 12 Jσ z1σ z2 ,  J >> ∆  Ferromagnetic coupling  • 24 •  00 ± 11  Lowest two energy eigenstates:  ± =  Energy eigenvalues:  ∆2 E± = m 2J  2  Entangled states  Two-Qubit Entanglement Equilibrium density matrix (J >> Τ , ∆):  ρ =P + + +P − − eq +  eq −  Concurrence (entanglement measure): W.K. Wootters, PRL 80, 2245 (1998)  C(ρ ) = P − P eq +  C((ρ) = 0, (i.e., unentangled) only if  P =P = eq +  • 25 •  eq −  1 2  i.e., T >> ∆ / J 2  eq −  Quantum Entanglement can persist in equilibrium  • 26 •  Summary: • Classical limit is large T (compared to energy spacings) and not long t (compared to decoherence time) • Without a Hamiltonian, the system will be classical after the decoherence time • With a well-defined Hamiltonian (stronger than noise) system may stay quantum mechanical even in equilibrium as long as T is small  • 27 •  Adiabatic Quantum Computation E If the excited state is not occupied its phase does not matter  . . .  . . .  gm  E1 E0 0  Temperature  1  Energy broadening (decoherence rate)  If gm >> T , γ, system will stay in the ground state throughout the computation  • What if gm < T , γ ? • What about the computation time? • 28 •  λ  Small Gap Regime Energy Spectrum  System Hamiltonian:  H = (1 − λ ) H B + λH P  λ  • 29 •  Small Gap Regime Energy Spectrum  System Hamiltonian:  H = (1 − λ ) H B + λH P  Effective two-state system Gap = gm  Landau-Zener physics approximately apply  • 30 •  Landau-Zener Transition H = − 12 (∆σ x +νtσ z )  Error  PLZ  E Landau-Zener formula: −πg m2  gm  1 − PLZ  / 2ν  PLZ = e ν ~ λ& ~ 1 / t  Success f  What happens if there is an environment?  • 31 •  λ  Landau-Zener Transition H = − 12 (∆σ x +νtσ z ) − Qσ z  Error  E Anticrossing is replaced by many anticrossings  gm  Success  No well-defined gap!  • 32 •  λ  Landau-Zener Probability at T=0 Landau-Zener probability is exactly the same as that for a closed system Spin environment: A.T.S. Wan, M.H.S. Amin, S.X. Wang, Int. J. Quant. Inf. 7, 725 (2009)  Harmonic oscillator environment: M. Wubs et al., PRL 97, 200404 (2006)  General environment: K. Saito et al., PRB 75, 214308 (2007) • 33 •  Error E gm  Success  λ  Landau-Zener Probability at finite T  T >> gm  P0 → 1/2  E T  There is always more chance of success than failure  What about computation time? The computation time scale remains the same M.H.S. Amin, P.J. Love. C.J.S. Truncik, PRL 100, 060503 (2008) M.H.S Amin, D.V. Averin, J.A. Nesteroff, PRA 80, 022107 (2009) • 34 •  gm  λ  Beyond 2-State Approximation Density matrix formalism: System  Bath  Interaction  Hamiltonian: Liouville equation: Find a differential equation that describes the evolution of the reduced density matrix.  • 35 •  Interaction Representation  Integrating  • 36 •  Interaction Representation Substituting back into the integrand  Differentiating + Tracing over the environment  Assumption: • 37 •  Instantaneous Energy Basis  Define  Thermal transitions • 38 •  Non-adiabatic transitions  Non-Markovian Master Equation  Non-adiabatic transitions  • 39 •  Thermal transitions  Non-Markovian Master Equation  Laplace Transformation:  [  ]  ~ ~ ~ ( s + iωnm ) ρ nm ( s ) + ∑ Rnmkl ( s ) + M nmkl ( s ) ( s ) ρ~kl ( s ) = ρ nm (0) k ,l  • 40 •  Perturbation around Markovian Solution If the change of within the response time of the environment (τB) is small we can do perturbation expansion in τB/tf Taylor expansion  • 41 •  leads to  Multi-Qubit System M.H.S Amin, C.J.S. Truncik, D.V. Averin, Phys. Rev. A 80, 022303 (2009)  System (Ising) Hamiltonian:  Random 16 qubit spin glass instances: • Randomly choose hi and Jij from {−1,0,1} and ∆i = 1 • Select small gap instances with one solution • 42 •  Markovian Approximation M.H.S Amin, C.J.S. Truncik, D.V. Averin, Phys. Rev. A 80, 022303 (2009)  Interaction Hamiltonian:  Spectral density Ohmic baths  • 43 •  Numerical Calculation M.H.S Amin, C.J.S. Truncik, D.V. Averin, Phys. Rev. A 80, 022303 (2009)  Closed system  Landau-Zener formula  Probability of success Open system  T = 25 mK η = 0.5 E = 10 GHz gmin = 10 MHz  Evolution Single qubit decoherence time T2 ~ 1 ns time  Computation time can be much larger than T2 • 44 •  What Is the Effect of Environment? Assumptions made: 1. Final Hamiltonian represents the correct problem 2. Coupling to environment is weak (energy levels are distinct except at the anticrossing) 3. There are only small number of energy levels near the ground state  If these assumptions fail to not hold, the conclusion would not hold • 45 •  The Effect of Environment •  Low frequency noise changes the final Hamiltonian which leads to solving a wrong problem  •  With strong coupling to environment, the ground state of system plus environment will not represent the ground state of the system  •  If there are many states available within energy T above the ground state, they will be occupied lowering the ground state probability  • 46 •  Open Question  Is there a threshold theorem for AQC?  • 47 •   Quantum Annealing and Quantum Phase Transition Mohammad Amin D-Wave Systems Inc.  Annealing as a Way of Optimization Ising Problem: Find a set of si = ±1 that minimizes N N r F ( s ) = ∑ hi si + ∑ J ij si s j , i =1  i , j =1  r s = [ s1 , s2 ,..., s N ]  F  Local Minimum Global Minimum  Ising Problem is NP-Hard •2•  r s  Classical (Thermal) Annealing Consider a physical system with energy: N  N  H = E  ∑ hi si + ∑ J ij si s j  i , j =1  i =1   E kBT kBT kBT kBT kBT  Local Minimum Global Minimum  •3•  r s  Thermal fluctuations take the system out of the local minima  Classical (Thermal) Annealing Consider a physical system with energy: N  N  H = E  ∑ hi si + ∑ J ij si s j  i , j =1  i =1   Boltzmann distribution:  Pn = Z −1e − En / T  Partition function:  Z = Tr e − H / T = ∑ e − En / T n  Thermal annealing: change T slowly from Tmax to 0 Or: keep T constant and change E from 0 to Emax  •4•  Quantum Annealing N  N  i =1  i , j =1  H P = ∑ hiσ iz + ∑ J ijσ izσ zj Hamiltonian:  N  x H = E  H P − Γ(t )∑ σ i  i =1    Tunneling amplitude  ∆ (t ) Γ(t ) = 2E  |ψ> ψ>  F  •5•  r s Global Minimum Quantum fluctuations (tunneling) keep the system out of the local minima  Quantum Annealing N  N  H P = ∑ hiσ + ∑ J ijσ izσ zj i =1  Hamiltonian:  z i  i , j =1  N  x H = E  H P − Γ(t )∑ σ i  i =1    ∆ (t ) Γ(t ) = 2E  Quantum annealing: change Γ slowly from Γmax to 0  •6•  Phase Transitions During annealing the system may go through a phase transition Phase transition: Transformation of a thermodynamic system from one phase to another due to some external change (e.g., temperature, pressure, etc.)  •7•  Classical Phase Transition Ferromagnetically coupled spins  H = − J ∑ σ izσ zj i, j  Large T::  T = 0:  Magnetization:  m ferromagnet  m=  paramagnet  N  z σ ∑ i i =1  Tc  •8•  T  Thermal Equilibrium Pi = Probability of finding the system in state i with energy Ei Boltzmann distribution: Partition function:  Pi =  e  Z  Z = ∑e i  •9•  − Ei / k B T  − Ei / k B T  Free Energy Let us write  Z = ∑ e − Ei / k B T = e − F / k B T i  F = −k BT ln Z  • 10 •  Free energy  Free Energy Let us write  e − Ei / k B T Pi = Z  • 11 •  Z = ∑ e − Ei / k B T = e − F / k B T i  F = −k BT ln Z = Ei − k BT ln Pi  Free Energy  Z = ∑ e − Ei / k B T = e − F / k B T  Let us write  i  e − Ei / k B T Pi = Z  F = −k BT ln Z = Ei − k BT ln Pi  ∑ P F = ∑ P E − k T ∑ P ln P i  i  • 12 •  i  i  i  B  i  i  i  Free Energy  Z = ∑ e − Ei / k B T = e − F / k B T  Let us write  i  e − Ei / k B T Pi = Z  F = −k BT ln Z = Ei − k BT ln Pi  ∑ P F = ∑ P E − k T ∑ P ln P i  i  ∑ P =1 i  i  i  B  i  i  i  i  F = E − TS  i  Average energy:  E = ∑ Pi Ei i  S = −k B ∑ Pi lnPi Equilibrium (Boltzmann) distribution is the i minimum of the free energy Entropy:  • 13 •  Second Order Phase Transition m=  Order parameter (magnetization)  N  z σ ∑ i i =1  T ~ Tc F  T > Tc F  T < Tc F  m  m  m  Continuous transition • 14 •  Tc  T  m  First Order Phase Transition Order parameter (magnetization)  m=  N  z σ ∑ i i =1  T > Tc  F  F  T < Tc  m  m  m  Discontinuous transition • 15 •  Tc  T  Quantum Phase Transition Hamiltonian:  H = − J ∑ σ izσ zj − Γ∑ σ ix i, j  Γ = 0:  • 16 •  i  Large Γ:  Quantum Phase Transition H = − J ∑ σ izσ zj − Γ∑ σ ix  Hamiltonian:  i, j  Large Γ:  Γ = 0:  Free energy:  E = −J ψ  i  z z σ ∑ iσj ψ i, j  F = ψ H ψ = E − ΓK  K= ψ  x σ ∑ iψ i  Minimum of the free energy is the ground state • 17 •  Classical vs. Quantum  Free energy: Measure of disorder:  Classical  Quantum  F = E − TS  F = E − ΓK  S = −k B ∑ Pi lnPi i  Free energy minimum: Disorder: Control parameter  • 18 •  K= ψ  x σ ∑ iψ i  Thermal equilibrium  Ground state  Thermal mixing  Superposition  T  Γ  AQC and Quantum Phase Transition AQC Hamiltonian: N  x H = (1 − λ ) H B + λH P = λ  H P − Γ ∑ σ i  i =1   ∆ (1 − λ ) Γ=  λ  • 19 •  λ=0  Complete disorder (superposition)  λ=1  Complete order (unique ground state)  λ = λc  Transition from disorder to order (quantum critical point)  2nd Order Quantum Phase Transition Large superposition  2N  E1  z =1  E0  E0 = 2 − N / 2 ∑ z  gmin  E  E0 = G 0  • 20 •  Localized state  λc  1  λ  2nd Order Quantum Phase Transition Large superposition  2N  E1  z =1  E0  E0 = 2 − N / 2 ∑ z  Order Parameter m=  Localized state  E0 = G 0  λc  1  λ  0  λc  1  λ  m  N  ∑σ i =1  • 21 •  gmin  E  z i  Spectral Gap S. Sachdev, “Quantum Phase Transitions”, Cambridge University Press (1999)  xi  xj  Correlation function:  σ σ z i  z j  − σ  z i  σ  z j  ~e  −| xi − x j |/ ξ  Correlation length  At the critical point all correlation lengths diverge  Universal behavior:  1 ξ~ | λ − λc |ν  g min ~ ξ − z • 22 •  Critical exponents  Spectral Gap For an infinitely large system  L→∞ g min → 0 ξ →∞  L  For a finite size system  ξ ~ L ~ N 1/ d For a 2D lattice (d = 2):  g min ~ ξ − z ~ L− z ~ N − z / d g min ~ N − z / 2  Dynamic critical exponent:  • 23 •  1≤ z ≤ 2  1st Order Quantum Phase Transition Large superposition  E0 = 2  −N / 2  2  N  ∑z z =1  E  Ek = L  E1  E0 = G  E0 0  Order Parameter m=  ∑σ i =1  • 24 •  λc  λ*  1  m  Global minimum  λ  mG = 2 wG − N  N  z i  Local minimum  gmin  0  λc  λ*  λ 1  Hamming weight  mL = 2 wL − N  Perturbation Expansion M. H. S. Amin and V. Choi, PRA 80, 062326 (2009)  Unperturbed Hamiltonian: Perturbation Hamiltonian: Small parameter:  HB can only cause single bit flips • 25 •  0th Order Perturbation  E 0  Local minimum  0  • 26 •  1  λ  Global minimum  1st Order Perturbation  E 0  Local minimum  0  • 27 •  1  λ  Global minimum  2nd Order Perturbation  E 0  Local minimum  0  • 28 •  1  λ  Global minimum  2nd Order Perturbation  E 0  Local minimum  E*  0  • 29 •  λ*  1  λ  Global minimum  Minimum Gap  Perturbed states  Perturbed Hamiltonian  E 0  Local minimum  gmin E*  0  • 30 •  λ*  1  λ  Global minimum  Minimum Gap Minimum bit flips = f  κ • 31 •  Hamming distance between global and local minima  What type of local minimum can create first order quantum phase transition? H = (1- λ) HB + λ HP Kinetic part  Potential part  E 0  Potential energy  Correction due to kinetic part  Local minimum  0  • 32 •  λc  λ*  1  λ  Global minimum  What type of local minimum can create first order quantum phase transition? Answer: A local minimum that can benefit more from the kinetic part than the global minimum The system should move more freely within the local than the global minimum (more possibilities with less energy cost) Example: Degenerate local minima  • 33 •  Global minimum  Maximum Independent Set (MIS) Problem An independent set in a graph is a set of vertices that are not connected directly to each other Maximum Independent Set  Independent Set  MIS is NP-hard • 34 •  (Weighted) MIS Hamiltonian   H P = −4∑ Wi xi − ∑ J ij xi x j  i, j  i   xi ∈ {0,1},  J ij > Wi ,W j  1  1  J ij 0  • 35 •  0  1 Wi  (Weighted) MIS Hamiltonian   H P = −4∑ Wi xi − ∑ J ij xi x j  i, j  i  1 + σ iz xi = 2  xi ∈ {0,1},  1  1  J ij  H P = −∑ hiσ iz + ∑ J ijσ izσ zj i  i, j  hi = 2Wi − ∑ J ij j  • 36 •  J ij > Wi ,W j  0  0  1 Wi  MIS Example  Maximum Independent Set (global minimum)  • 37 •  MIS Example  27 Maximum Independent Sets (global minima)  • 38 •  MIS Example  • 39 •  MIS Example  • 40 •  MIS Example M. H. S. Amin and V. Choi, PRA 80, 062326 (2009)  27-fold degenerate local minimum  Non-degenerate global minimum (MIS)  Degenerate local minima • 41 •  Global minimum  MIS Example  (b)  ≡ WMIS  • 42 •  Weighted MIS J= 2  Wi = W  Wi = 1  • 43 •  ∆=1  Spectral Gap W = 1.8  0  • 44 •  λ  1  Two Interesting Quantities Magnetization (as an order parameter):  Spread of the wave-function:  ψ0  1 m = i ∑ m i =1  m S= N 2  S = fraction of states participating in the superposition  • 45 •  Order Parameter & Wave Function Spread W = 1.8  • 46 •  Minimum Gap Barrier height ∆U = 4(2−W)  0  ∆E = 12(2−W)  0  as W  ∆U ∆E  • 47 •  2  Minimum Gap Barrier height ∆U = 4(2−W)  0  ∆E = 12(2−W)  0  as W  The gap is exponentially sensitive to W • 48 •  2  Controversy M. H. S. Amin and V. Choi, PRA 80, 062326 (2009) B. Altshuler, H. Krovi, and J. Roland, arXiv:0908.2782, PNAS 107, 12446 (2010) (See Altshuler’s presentation on July 23) E. Farhi, J. Goldstone, D. Gosset, S. Gutmann, H. B. Meyer and P. Shor, arXiv:0909.4766 A.P. Young, S. Knysh, V.N. Smelyanskiy, PRL 104, 020502 (2010) T. Jorg, F. Krzakala, G. Semerjian, and F. Zamponi, PRL 104, 207206 (2010) S. Knysh, V.N. Smelyanskiy, arXiv:1005.3011 V. Choi, arXiv:1004.2226 (See Choi’s presentation on July 23) N. Dickson, M.H.S. Amin, (See Dickson’s poster on July 24) . . . • 49 •   Quantum Annealing With Superconducting Qubits Mohammad Amin D-Wave Systems Inc.  Basic Circuit Elements Q Capacitance:  2 Q 1 E = CV 2 = 2 2C  Inductance:  1 2 Φ2 E = LI = 2 2L  Josephson junction:  •2•  Φ  φ  E = − E J cos φ  RF-SQUID Φ  •3•  φ  Q  Q2 Φ2 E= + − E J cos φ 2C 2 L  RF-SQUID Φ  φ  Q2 Φ2 E= + − E J cos φ 2C 2 L  Q  2πΦ Flux quantization: φ = Φ0  & =V = Faraday’s law: Φ  Φ2 2πΦ V (Φ ) = − E J cos 2L Φ0  1 &2 E = CΦ + V (Φ ), 2 Newtonian mechanics:  1 2 E = mx& + V ( x) 2  Kinetic energy •4•  Q C  mass  Potential energy  Comparing RF-SQUID with a particle particle position  x  Φ  mass  m  C  p = mx&  & = CV Q = CΦ  [ x , p ] = ih  [ Φ , Q ] = ih  momentum commutators kinetic energy Potential energy •5•  SQUID  1 2 p2 mx& = 2 2m  1 & 2 Q2 CΦ = 2 2C  V (Φ )  V (x)  RF-SQUID Hamiltonian Q2 H= + V (Φ ) 2C (Φ − Φ x ) 2 2πΦ V (Φ ) = − E J cos 2L Φ0  •6•  Φ  φ Φx  Q  RF-SQUID Hamiltonian Q2 H= + V (Φ ) 2C (Φ − Φ x ) 2 2πΦ V (Φ ) = − E J cos 2L Φ0  1 H ≈ − [εσ z + ∆σ x ] 2  V (Φ )  0  φ  Φ  Q  1  Φx 0  1  ∆ tunneling amplitude •7•  Φ x ≈ 12 Φ 0  Φ  CJJ RF-SQUID Qubit 0  1  δU ε  1 H = − [εσ z + ∆(δU )σ x ] 2 Control knobs:  Φ1x controls energy bias ε Φ2x controls barrier height δU  •8•  Actual Qubit Harris et al, arXiv:1004.1628 (2010)  Ip compensator  Inductance tuner •9•  Junction asymmetry compensator  Readout  Programmable Magnetic Memory (PMM) Johnson et al., Supercond. Sci. Technol. 23, 065004 (2010)  • 10 •  Fabrication  • 11 •  Eight-Qubit Unit Cell Qubit #1  • 12 •  128 Qubits Chip  • 13 •  Wire Bounded Chip  • 14 •  Pulse Tube Dilution Refrigerator  • 15 •  Annealing Process Annealing happens by raising barrier height ∆U, which provides Γ(t)  ε  ε Time  At fixed external flux bias Φ1x, raising barrier height will also changes the energy bias ε • 16 •  Annealing in Our Hardware N  N  H P = ∑ hiσ + ∑ J ijσ izσ zj i =1  Hamiltonian:  z i  i , j =1  N  x H = E (t ) H P − Γ(t )∑ σ i  i =1    ∆(t ) Γ(t ) = 2 E (t )  Γ(t) changed from Γmax to 0: Quantum annealing! E(t) changes from 0 to Emax: Classical annealing! • 17 •  Question: Is it quantum or classical annealing? Answer: It depends on which one of quantum or thermal fluctuations are stronger  How can we determine this experimentally? • 18 •  Macroscopic Quantum Tunneling Current biased Josephson junction:  U  I  φ  Classical escape rate:  Γ = (ω p / 2π ) exp(− ∆U / k BT )  ∆U  Quantum escape (tunneling) rate:  φ  • 19 •  Γ = independent of T  Saturation due to quantum tunneling Classical prediction  • 20 •  Classical Annealing No Dynamics  Dynamics  tfreeze  Time  Γ = (ω p / 2π ) exp(−∆U freeze / k BT ) = small number  • 21 •  Therefore:  ∆U (t freeze ) = ∆U freeze ∝ T  If ∆U (t ) ∝ t  then  t freeze ∝ T  very similar to Tesc  Quantum Annealing No Tunneling  Tunneling  tfreeze Quantum mechanically tunneling amplitude exponentially depends on ∆U but not T Therefore  Γ = T − indepdent  or  t freeze = T − independent • 22 •  Time  h-Ramping Experiment H = h(t )σ z − Γ(t )σ x E (t )  h(t) h0  td  tfreeze  If td < tfreeze then the final probability is: P0(h=h0) > 0.5  • 23 •  t  h-Ramping Experiment h(t) h0  H = h(t )σ z − Γ(t )σ x E (t )  tfreeze td If td < tfreeze then the final probability is: P0(h=h0) > 0.5 If td > tfreeze then the final probability is: P0(h=0) = 0.5 P0(td) 0.5  tfreeze • 24 •  td  t  Quantum Simulations  Single-Qubit Data Experimental Data 0  P0(td)  P0(td) td [µ µs] Classical Simulations 100.00%  20 mK 90.00%  td [µ µs] tfreeze  Temperature is measured independently using MRT  50 mK  80.00%  P0(td)  70.00%  90 mK  60.00% 50.00% 40.00% 60  • 25 •  65  70  75  80  td [µ µs]  85  90  95  100  Freeze-out Time Classical prediction Freeze-out time measurement  Saturation due to quantum tunneling • 26 •  Devoret et al., PRL (1985)  Experiment vs. Simulations 4-state modeling  2-state modeling  All simulations are done with no • 27 •  fitting parameter  Experiment vs. Simulations rf-SQUID behavior at different temperatures: Up to 40 mK 2-level quantum system Up to 80 mK 4-level quantum system Above 100 mK Classical system  • 28 •  Can we do this for more than one qubit?  • 29 •  8-Qubit Ferromagnetic Chain  Hamiltonian:  H = H P − Γ(t )∑ σ ix E (t ) i N  N  i =1  i , j =1  H P = ∑ hiσ iz − J ∑ σ izσ zj • 30 •  8-Qubit Ferromagnetic Chain  Domain wall can be in any of the 7 sites with probability 1/7  • 31 •  8-Qubit Ferromagnetic Chain  h << J  Domain wall most probably on the right site  • 32 •  8-Qubit Ferromagnetic Chain  h << J  Ground state • 33 •  Question:  Is the ground state reached via classical or quantum annealing?  • 34 •  8-Qubit h-Ramping Experiment  h << J  H = H P (h) − Γ(t )∑ σ ix E (t ) i  td < tfreeze  P0(h=h0) > 1/7  h(t) h0  td • 35 •  tfreeze  t  8-Qubit h-Ramping Experiment  h << J  H = H P (h) − Γ(t )∑ σ ix E (t ) i  td < tfreeze  P0(h=h0) > 1/7  td > tfreeze  P0(h=0) = 1/7  h(t) h0  tfreeze td • 36 •  t  8-Qubit h-Ramping Experiment  h << J  H = H P (h) − Γ(t )∑ σ ix E (t ) i  td < tfreeze  P0(h=h0) > 1/7  td > tfreeze  P0(h=0) = 1/7  P0(td)  1/7  tfreeze • 37 •  td  0  8-Qubit Experimental Results  P0(td)  Saturation of the freeze-out time cannot be explained by classical physics • 38 •  Modeling The System Write down a Hamiltonian and solve it both Classically: Using Langevin equation Quantum Mechanically: Using density matrix approach  • 39 •  RF-SQUID Hamiltonian Hamiltonian:  Interaction with environment: Noise spectral density:  • 40 •  All parameters, including noise, are determined via independent experiments  Extracting Noise Parameters  A is determined from 1/f noise measurement  η is extracted from measuring the Macroscopic Resonant Tunneling (MRT)  Γ(ε) Γ(ε) ε • 41 •  Extracting Noise Parameters  • 42 •  Classical Modeling Langevin equation: Force Φ1 x = 2π Φ0 F ( x) = −  Dissipation  Noise  Fluctuation dissipation theorem:  • 43 •  dU dx  Classical Modeling Each rf-SQUID potential has 2 space variables (x1,x2) and 2 velocities (v1,v2) For 8 qubits, we solve Langevin equation on a 16 dimensional potential We run the program for more than 2000 times and find the probabilities statistically We use distributed computation (AQUA@home): ~10,000 cores (>5500 computers in 78 countries) ~2,000,000 CPU core hours (>200 years) • 44 •  Quantum Modeling Quantum mechanically energy is quantized  Qubit Model: Keep lowest 2 energy levels Qudit Model: Keep lowest d energy levels  • 45 •  4-Level Qudit Model  Logical 0  Logical 1  10  All levels within each well are logically equivalent  00  11 01  00 Ancilla qubit • 46 •  Logical qubit  Qubit Representation of Qudits  XZ coupling  • 47 •  XX coupling  Multi-Qubit System  • 48 •  Multi-Qubit System  Couple to each qubit an ancilla qubit with XX+XZ coupling  • 49 •  Multi-Qubit System Coupled system Hamiltonian: Original qubit Hamiltonian  Interaction Hamiltonian: All parameters are directly extracted from the rf-SQUID Hamiltonian The final ground state is unaffected by ancilla qubits • 50 •  Experiment vs. Simulations 8 Qubit Chain  Single Qubit  Classical and quantum simulations agree with experiment with no free parameters • 51 •  Collaborators: Experiment: A.J. Berkley, E. Chapple, S. Gildert, R. Harris, J. Johansson, M.W. Johnson, T. Lanting, B. Wilson Chip Design and Fabrication: P. Bunyk, E. Ladizinsky, N. Ladizinsky, T. Oh, E. Tolkacheva, Engineering and Technical Support: F. Cioata, C. Enderud, R. Neufeld, I. Perminov, C. Petroff, L. Paulson, C. Rich, P. Spear, M. Thom, S. Uchaikin, J. Wang, A. Yarovoy Simulations: N. Dickson, F. Hamze, K. Karimi, C. Truncik • 52 •  `

#### Cite

Citation Scheme:

Citations by CSL (citeproc-js)

#### Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
```                        ```
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
`http://iiif.library.ubc.ca/presentation/dsp.59370.1-0040933/manifest`