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

### Adiabatic Quantum Computation Mohammad, Amin 2010-07-21

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

#### Download

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 ]
Metadata
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. • 2 • 1. Introduction to AQC 2. Effect of noise on AQC 3. Quantum annealing and quantum phase transition 4. Quantum annealing with superconducting qubits Topics: • 3 • Hamiltonian Schrödinger equation: ψψ H dt d i =h Planck constant Time evolution operator: )0()()( ψψ tUt = h/)( iHtetU −=For time-independent H: Quantum Evolution • 4 • ψ t H 0 Hamiltonian is applied only at the time of gate operation ψU Quantum Gates δt • 5 • Eigenstate Eigenvalue nnn EH ψψ = Question: What happens if the system starts in an eigenstate? Answer:  Nothing! The system will stay in the same eigenstate n tiE n iHt n neet ψψψ hh //)( −− == nψψ =)0( Eigenstates and Eigenvalues: • 6 • Adiabatic Quantum Computation (AQC) E. Farhi et al., Science 292, 472 (2001) System Hamiltonian: H = (1− λ) HB + λ HP E λ gm E0 E1 10 . . . . . . • 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 • 7 • Computation Time Uncertainty of energy (superposition in energy basis) Time spent on the energy level Energy-time uncertainty relation:  hEt >⋅δδ Planck constant • 8 • Computation Time E tδt tf Ef Energy-time uncertainty relation:  hEt >⋅δδ 2 m f f f m f g hE t E g t t >⇒= δUniform time sweep: m ff g h ttt >⇒        ~ δNon-uniform time sweep: m m g h tgE >⇒< δδ Optimal Minimum gap • 9 • Landau-Zener Problem E t0 P0 2-State Hamiltonian: ( )zxm tgH σνσ +−= 2 1 ν pi h gm etPtP 22 )(       0)( 11 − =+∞=⇒=−∞= Exact solution P1 21       1)( 22 m f f t hE g f f f g hE tetP t E ff m >>⇒<<≈⇒= − pi ν • 10 • Adiabatic Theorem 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) . . . 2 ]1,0[ 1/0max m f g ddH t λλ∈ >> • 11 • Adiabatic Theorem 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) . . . 2 ]1,0[ 1/0max m f g ddH t λλ∈ >> • 12 • 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) • 13 • Universal AQC Consider a quantum algorithm with n gates represented by unitary operators: nUUU ,  ...  ,, 21 012  ... ψψ UUU ll =After l gates: 01211   ... ψψ UUUnn −− =Solution: Therefore                                   andlll U ψψ 11 ++ = lll U ψψ 1 1 − − = Write down a Hamiltonian with         being in its ground state 1−nψ 01 ψψψ == −nnn UReset: Seth Lloyd, arXiv:0805.2757 • 14 • Pointer or Clock Qubits Define orthogonal states: nll , ... ,0   , = 0 0000...11  ... 0100...02 0010...01 0001...00 = =− = = = n n They can be represented by n additional qubits: • 15 • Hamiltonian Define states ∑ − = ⊗=Ψ 1 0 /21 n l l nkli k le n ψpi [ ]∑− = − ++ +⊗++⊗−= 1 0 1 11 11 n l llP llUllUH ∑∑ = − − = + −⊗−+⊗−=Ψ n l l nkli n l l nkli kP le n le n H 1 1 /2 1 0 1 /2 1111 ψψ pipi ( ) ( ) ( ) k n l l nklinkinki n l l nlkinlki nk le n ee lee n Ψ−= ⊗+−= ⊗+−= ∑ ∑ − = − − = +− /2cos2 1  1  1 0 /2/2/2 1 0 /)1(2/)1(2 pi ψ ψ pipipi pipi Eigenstates of H • 16 • Ground State Eigenstates: ∑ − = ⊗=Ψ 1 0 /21 n l l nkli k le n ψpi kkkP EH Ψ=Ψ )/ 2cos(2 nkEk pi−= 2        0 0 −=⇒= Ek n Ek pi2cos2        1 1 −=⇒= 2 2 01 22 cos12 nn EE pipi ≈      −=− Ground state: First excited state: Energy gap: Eigenvalues: • 17 • Adiabatic Evolution [ ]∑− = − ++ +⊗++⊗−= 1 0 1 11 11 n l llP llUllUH PB HHH λλ +−= )1( ( ) 00100 00 ==⊗−+==−= llllH B ψψη Initial Hamiltonian: Final Hamiltonian: Minimum gap happens at λ = 1, therefore 2 22 n gm pi ≈ Computation time ~ n4       n = # of gates • 18 • Universality AQC is computationally equivalent to gate model quantum computation They can be mapped to each other with polynomial overhead • 19 • Practicality [ ]∑− = − ++ +⊗++⊗−= 1 0 1 11 11 n l llP llUllUH 2-qubit interaction2-qubit interaction 4-qubit interaction + = 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) Hp is not diagonal in computation basis Not practical! • 20 • Adiabatic Quantum Optimization Diagonal (in computation basis) Off-diagonal (in computation basis) H = (1− λ) HB + λ HP Hamiltonian: The final state is a classical state that minimizes the energy of Hp • 21 • Adiabatic Grover Search Grover search algorithm )( NOt f = Classical search algorithm:  )(NOt f = Unstructured search problem: Find state m in a data base containing N = 2n entries with no structure • 22 • Adiabatic Grover Search (N-2)-fold degenerate nE H = (1− λ) HB + λ HP mmH P −=1 λ ++−=1BH n N z Nz N 2        ,1 1 0 ==+ ∑ − = N gm 1 = Linear time sweep:  N g t m f ~ 1 ~ 2 Classical speed Optimal time sweep:  N g t m f ~ 1 ~ Grover speed J. Roland and N. Cerf, PRA 65, 042308 (2002) Not practical! • 23 • Ising Problem ],...,,[        ,)( 21 1 1, n n i n ji jiijii ssssssJshsF =+=∑ ∑ = = rr Find a set of si = ±1 that minimizes Ising problem is NP-Hard • 24 • Ising Hamiltonian Diagonal (in σz basis) Off-diagonal (transverse) ],...,,[        ,)( 21 1 1, n n i n ji jiijii ssssssJshsF =+=∑ ∑ = = rr Find a set of si = ±1 that minimizes H = (1− λ) HB + λ HPHamiltonian: ∑ ∑ = = += n i n ji z j z iij z iiP JhH 1 1, σσσ ∑ = ∆−= n i x iBH 1 σ • 25 • Open Question How does computation time scale with n? G. Rose et al., arXiv:1006.4147 Effect of Environment on Adiabatic Quantum Computation Mohammad Amin D-Wave Systems Inc. • 2 • 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 • 3 • nnnS S EH HHHH ψψ = ++= intenv Open Quantum Sysytem Environment (Bath) InteractionSystem • 4 • nnnS S EH HHHH ψψ = ++= intenv Question: 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. Open Quantum Sysytem E0 E1 E2 E3 . . . • 5 • nnnS S EH HHHH ψψ = ++= intenv Open Quantum Sysytem E0 E1 E2 E3 . . . Answer: System will relax to the ground state. Question: Assume weak coupling to environment and En−E0>>T, what happens if the system starts in an excited state? • 6 • Quantum Coherence Single qubit Hamiltonian: xH σ∆−= 21 0 1 Tunneling ∆ 00 −=zσ 11 =zσ Logical basis: • 7 • Quantum Coherence Single qubit Hamiltonian: xH σ∆−= 21 2        , 2 10 ∆ = ± =± ± mEEigenstates and Eigenvalues: 0 1 Energy gap = ∆  2 10 + =+  2 10 − =− • 8 • Quantum Coherence Single qubit Hamiltonian: xH σ∆−= 21 2        , 2 10 ∆ = ± =± ± mEEigenstates and Eigenvalues: 0 1  2 0)0( −++===tψInitializing in state “0”: • 9 • Quantum Coherence Single qubit Hamiltonian: xH σ∆−= 21 2        , 2 10 ∆ = ± =± ± mEEigenstates and Eigenvalues: 0 1  2 0)0( −++===tψInitializing in state “0”: 1 2 sin  0 2  cos 2 )( 2/2/ hh hh tit ee t titi ∆ + ∆ = −++ = ∆−∆ ψ Tunneling ∆ • 10 • Quantum Coherence )/ cos1( 2 1)(0)( 20 htttP ∆+== ψ Probability of finding the qubit in state “0”: Coherent Oscillations Single qubit Hamiltonian: xH σ∆−= 21 0 1 Tunneling ∆ • 11 • What happens if there is an environment? • 12 • Open Quantum System Single qubit Hamiltonian: envint21 HHH x ++∆−= σ ±± + ∆ = ± ≈± EE δ 2        , 2 10 m Eigenstates and Eigenvalues: Uncertainty in Energy Energy-time uncertainty relation:  hEt >⋅δδ Relaxation time T1 • 13 •  TTT ϕ 1 2 11 12 += Pure dephasing due to classical noise Dephasing Time  2 )( /)( −++ ≈ +∆− htEie t δ ψWave function: h /tE ⋅= δδϕUncertainty in phase:  /~ Et δhPhase information is lost within Dephasing time T2 • 14 • Density Matrix Approach Pure state density matrix: ψψρ = aaaPa ρψ == 2 ][Tr AA ρψψ = All information can be extracted from the density matrix: Time evolution of the density matrix: Schrodinger equation         Liouville equation ],[ ρρ Hi h & −= Quantum mechanics can be formulated in terms of the density matrix • 15 • Pure State vs. Mixed State Pure state density matrix:         = +++== 2* *2 2**2  11011000 ββα αβα ββααβαψψρ 10 βαψ += Nonzero off-diagonal elements represent quantum superposition Mixed state density matrix:       =+= 1 0 10 0 0 1100 P P PPρ Classical probabilities • 16 • Open Quantum System Hamiltonian: Bath InteractionSystem SBSBSB ψψρ =Total (system + bath) density matrix: ][Tr SBBS ρρ =Reduced (system) density matrix: Bn n BnB xx ΨΨ=∑][Tr Environment eigenfunctions • 17 • Entanglement with Environment [ ] [ ] [ ][ ] [ ]      == 11 2 01 * 10 * 00 2 TrTr TrTr Tr BBBBBB BBBBBB SBSBBS ψψβψψβα ψψαβψψαψψρ 10 10        10 BBSBS ψβψαψβαψ ⊗+⊗=→+= Entanglement with environment decoheres the qubit and generates mixed state ≈0 ≈0 ≈1 ≈1 0  if 10 ≈BB ψψ         = 2 2 0 0 β αρS Decoherence • 18 • Coherent Oscillations         = ∆− ∆ 2 1 2 1 2 1 2 1 ti ti e eρ Diagonal part of the density matrix does not change Off-diagonal part oscillates 1 2 sin  0 2  cos 2 )( 2/2/ tit ee t titi ∆ + ∆ = −++ = ∆−∆ ψ Density matrix in energy basis: Density matrix in computation basis:         ∆ ∆− == ∆ ∆ 2 2 2 22 2 sinsin sincos ti it t tψψρ • 19 • Open System Oscillations         −+ −+ = − −− −∆− −∆− ++ 12 21 / 2 1/ 2 1 / 2 1/ 2 1 )( )( TteqeqTtti TttiTteqeq ePPee eeePPρ Density matrix in energy basis (weak coupling limit): TETE TE eq ee eP // / −+ ± −− − ± + = Equilibrium (Boltzmann) Distribution Dephasing (T2) process Relaxation (T1) process         → − +∞→ eq eq t P P 0 0ρ Is this a completely classical state? • 20 • Equilibrium State Density matrix in energy basis:        = − + eq eq P P 0 0ρ         − − = −+ −+ 1 1 2 1 eqeq eqeq PP PPρ Density matrix in computation basis (“0” , “1”): ∆>>== −+ TPP eqeq     i.e.,    21 ρ is diagonal in logical basis only if Signature of coherent mixture • 21 • Quantum Superposition (coherent mixture) can persist in equilibrium • 22 • Coherent Tunneling ∆<= 2/1 Tγ 0 1 γ = broadening Energy gap = ∆ ), cos1(0)(0)(  210 tettP t ∆+== −γρ Decoherence rate Coherent oscillations Well-defined gap • 23 • Incoherent Tunneling 0 1 γ = broadeningEnergy gap = ∆ rate  tunnelingIncoherent             ),1()( 2 2 1 0  γ ∆ =Γ+= Γ− tetP Gap not well-defined ∆>= 2/1 TγIf decoherence rate Incoherent tunneling is still a quantum effect • 24 • Two-Qubit Example Hamiltonian: ∆>>−+∆−= JJH zzxx            ,)( 21212121 σσσσ J E 2  2 1100 2∆ = ± =± ± m Energy eigenvalues: Lowest two energy eigenstates: Entangled states Ferromagnetic coupling • 25 • Concurrence (entanglement measure): W.K. Wootters, PRL 80, 2245 (1998) eqeq PPC −+ −=)(ρ Two-Qubit Entanglement −−+++= −+ eqeq PPρ Equilibrium density matrix (J >> Τ , ∆): JTPP eqeq /    i.e.,    221 ∆>>== −+ C(ρ) = 0, (i.e., unentangled) only if • 26 • Quantum Entanglement can persist in equilibrium • 27 • • With a well-defined Hamiltonian (stronger than noise) system may stay quantum mechanical even in equilibrium as long as T is small 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 • 28 • Adiabatic Quantum Computation E λ gm E0 E1 10 . . . . . . If   gm >> T , γ,  system will stay in the ground state throughout the computation Temperature        Energy broadening (decoherence rate) • What if  gm < T , γ  ? • What about the computation time? If the excited state is not occupied its phase does not matter • 29 • Small Gap Regime Energy Spectrum PB HHH λλ +−= )1( System Hamiltonian: λ • 30 • Small Gap Regime Energy Spectrum Effective two-state system Gap = gm Landau-Zener physics approximately apply PB HHH λλ +−= )1( System Hamiltonian: • 31 • Landau-Zener Transition What happens if there is an environment? gm f g LZ t eP m /1~~ 2/2 λν νpi & − = Error Success Landau-Zener formula: )(21 zx tH σνσ +∆−= λ E LZP LZP−1 • 32 • Landau-Zener Transition gm Error Success zzx QtH σσνσ −+∆−= )(21 Anticrossing is replaced by many anticrossings No well-defined gap! λ E • 33 • 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) gm Error Success λ E • 34 • Landau-Zener Probability at finite T 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) gm E λ T >> gm P0 → 1/2 T There is always more chance of success than failure What about computation time? • 35 • Beyond 2-State Approximation Hamiltonian: Bath InteractionSystem Liouville equation: Find a differential equation that describes the evolution of the reduced density matrix. Density matrix formalism: • 36 • Interaction Representation Integrating • 37 • Interaction Representation Differentiating + Tracing over the environment Assumption: Substituting back into the integrand • 38 • Instantaneous Energy Basis Define Non-adiabatic transitions Thermal transitions • 39 • Non-Markovian Master Equation Non-adiabatic transitions Thermal transitions • 40 • Non-Markovian Master Equation Laplace Transformation: [ ] )0()(~ )(~)(~)(~)( , )( nmkl lk snmklnmklnmnm ssMsRsis ρρρω =+++ ∑ • 41 • If the change of         within the response time of the environment (τB) is small we can do perturbation expansion in τB/tf Perturbation around Markovian Solution Taylor expansion                                   leads to • 42 • Multi-Qubit System System (Ising) Hamiltonian: • Randomly choose hi and Jij from {−1,0,1} and ∆i = 1 • Select small gap instances with one solution Random 16 qubit spin glass instances: M.H.S Amin, C.J.S. Truncik, D.V. Averin, Phys. Rev. A 80, 022303 (2009) • 43 • Markovian Approximation Interaction Hamiltonian: Ohmic baths Spectral density M.H.S Amin, C.J.S. Truncik, D.V. Averin, Phys. Rev. A 80, 022303 (2009) • 44 • Numerical Calculation Probability of success Evolution time Closed system Landau-Zener formula Open system T = 25 mK η = 0.5 E = 10 GHz gmin = 10 MHz Single qubit decoherence time T2 ~ 1 s Computation time can be much larger than T2 M.H.S Amin, C.J.S. Truncik, D.V. Averin, Phys. Rev. A 80, 022303 (2009) • 45 • 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 • 46 • 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 • 47 • Open Question Is there a threshold theorem for AQC? Quantum Annealing and Quantum Phase Transition Mohammad Amin D-Wave Systems Inc. • 2 • Annealing as a Way of Optimization ],...,,[        ,)( 21 1 1, N N i N ji jiijii ssssssJshsF =+=∑ ∑ = = rr Ising Problem: Find a set of si = ±1 that minimizes Ising Problem is NP-Hard s r F Global Minimum Local Minimum • 3 • Classical (Thermal) Annealing s r E Global Minimum Local Minimum         += ∑ ∑ = = N i N ji jiijii ssJshEH 1 1, Consider a physical system with energy: kBT kBT kBT kBT kBT Thermal fluctuations take the system out of the local minima • 4 • Classical (Thermal) Annealing ∑ −− −− == = n TETH TE n n n eeZ eZP // /1 Tr Boltzmann distribution: Partition function: Thermal annealing: change T slowly from Tmax to 0 Or: keep T constant and change E from 0 to Emax         += ∑ ∑ = = N i N ji jiijii ssJshEH 1 1, Consider a physical system with energy: • 5 • Quantum Annealing ∑ ∑ = = += N i N ji z j z iij z iiP JhH 1 1, σσσ Hamiltonian:       Γ−= ∑ = N i x iP tHEH 1 )( σ E t t 2 )()( ∆=Γ Tunneling amplitude s r F Global Minimum |ψ> Quantum fluctuations (tunneling) keep the system out of the local minima • 6 • Quantum Annealing Quantum annealing:  change Γ slowly from Γmax to 0 ∑ ∑ = = += N i N ji z j z iij z iiP JhH 1 1, σσσ Hamiltonian:       Γ−= ∑ = N i x iP tHEH 1 )( σ E t t 2 )()( ∆=Γ • 7 • 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.) • 8 • Classical Phase Transition Ferromagnetically coupled spins ∑−= ji z j z iJH , σσ T = 0: Large T: Magnetization: paramagnet T m Tc ∑ = = N i z im 1 σ ferromagnet • 9 • Thermal Equilibrium Z eP TkE i Bi /− =Boltzmann distribution: Partition function: ∑ −= i TkE BieZ / Pi = Probability of finding the system in state i with energy Ei • 10 • Free Energy TkF i TkE BBi eeZ // −− ==∑ ZTkF B ln−= Let us write Free energy • 11 • Free Energy TkF i TkE BBi eeZ // −− ==∑ iBiB PTkEZTkF lnln −=−=Z eP TkE i Bi /− = Let us write • 12 • Free Energy TkF i TkE BBi eeZ // −− ==∑ iBiB PTkEZTkF lnln −=−=Z eP TkE i Bi /− = ∑∑∑ −= i iiB i ii i i PPTkEPFP ln Let us write • 13 • Free Energy TkF i TkE BBi eeZ // −− ==∑ iBiB PTkEZTkF lnln −=−=Z eP TkE i Bi /− = ∑∑∑ −= i iiB i ii i i PPTkEPFP ln TSEF −= ∑= i ii EPE i i iB PPkS ∑−= ln Average energy: Entropy: Let us write 1=∑ i iP Equilibrium (Boltzmann) distribution is the minimum of the free energy • 14 • Second Order Phase Transition Order parameter (magnetization) m F T > Tc F m T ~ Tc F m T < Tc Continuous transition T m Tc ∑ = = N i z im 1 σ • 15 • First Order Phase Transition ∑ = = N i z im 1 σOrder parameter (magnetization) m F T < Tc m F T > Tc Discontinuous transition T m Tc • 16 • Quantum Phase Transition ∑∑ Γ−−= i x i ji z j z iJH σσσ , Hamiltonian: Large Γ:Γ = 0: • 17 • Quantum Phase Transition Hamiltonian: KEHF Γ−== ψψFree energy: ψσσψ ∑−= ji z j z iJE , ψσψ ∑= i x iK ∑∑ Γ−−= i x i ji z j z iJH σσσ , Minimum of the free energy is the ground state Large Γ:Γ = 0: • 18 • Classical vs. Quantum KEF Γ−=Free energy: Measure of disorder: ψσψ ∑= i x iK Classical Quantum TSEF −= i i iB PPkS ∑−= ln Free energy minimum: Thermal equilibrium        Ground state Control parameter T Γ Disorder: Thermal mixing            Superposition • 19 • AQC and Quantum Phase Transition AQC Hamiltonian: λ λ σλλλ )1( )1( 1 −∆ =Γ       Γ−=+−= ∑ = N i x iPPB HHHH λ = 0 Complete disorder (superposition) λ = 1 Complete order (unique ground state) λ = λc Transition from disorder to order(quantum critical point) • 20 • 2nd Order Quantum Phase Transition E λ gmin E0 E1 10 λc GE =0 Large superposition Localized state ∑ = − = N z N zE 2 1 2/ 0 2 • 21 • 2nd Order Quantum Phase Transition E λ gmin E0 E1 10 λc GE =0 λλc m 10 ∑ = = N i z im 1 σ Order Parameter Localized stateLarge superposition ∑ = − = N z N zE 2 1 2/ 0 2 • 22 • Spectral Gap ξσσσσ /||~ ji xxzj z i z j z i e −− − Correlation function: xi xj Correlation length At the critical point all correlation lengths diverge νλλξ || 1 ~ c− zg −ξ~min Universal behavior: Critical exponents S. Sachdev, “Quantum Phase Transitions”, Cambridge University Press (1999) • 23 • Spectral Gap For an infinitely large system L ∞→ξ 0min →g dzzz NLg /min ~~~ −−−ξdNL /1~~ξ For a finite size system For a 2D lattice (d = 2): 2/min ~ zNg − Dynamic critical exponent: 21 ≤≤ z ∞→L • 24 • 1st Order Quantum Phase Transition E E0 E1 0 λ1λc gmin λ* GE =0 LEk = Large superposition ∑ = − = N z N zE 2 1 2/ 0 2 Local minimum m λ 10 λc Nwm GG −= 2 λ* Nwm LL −= 2 ∑ = = N i z im 1 σ Order Parameter Hamming weight Global minimum • 25 • Perturbation Expansion Unperturbed Hamiltonian: Perturbation Hamiltonian: HB can only cause single bit flips Small parameter: M. H. S. Amin and V. Choi, PRA 80, 062326 (2009) • 26 • 0th Order Perturbation E 0 λ1 Local minimum 0 Global minimum • 27 • 1st Order Perturbation E 0 λ1 Local minimum 0 Global minimum • 28 • 2nd Order Perturbation E 0 λ1 0 Local minimum Global minimum • 29 • 2nd Order Perturbation E 0 λ1λ* 0 Local minimum Global minimum E* • 30 • Minimum Gap E 0 λ1 gmin λ* 0 Local minimum Global minimum E* Perturbed states Perturbed Hamiltonian • 31 • Minimum Gap Minimum bit flips = f Hamming distance between global and local minima κ • 32 • What type of local minimum can create first order quantum phase transition? H = (1- λ) HB + λ HP Kinetic part Potential part E 0 λ1λc λ* 0 Local minimum Global minimum Potential energyCorrection due to kinetic part • 33 • 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) Degenerate local minima Global minimum Example: • 34 • 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 MIS is NP-hard Independent Set • 35 • (Weighted) MIS Hamiltonian 1 1 1 0 0 jiiji WWJx ,      },1,0{ >∈       −−= ∑∑ ji jiij i iiP xxJxWH , 4 iW ijJ • 36 • (Weighted) MIS Hamiltonian       −−= ∑∑ ji jiij i iiP xxJxWH , 4 ∑ ∑∑ −= +−= + = j ijii ji z j z iij i z iiP z i i JWh JhH x 2 2 1 , σσσ σ 1 1 1 0 0 jiiji WWJx ,      },1,0{ >∈ iW ijJ • 37 • MIS Example Maximum Independent Set (global minimum) • 38 • MIS Example 27 Maximum Independent Sets (global minima) • 39 • MIS Example • 40 • MIS Example • 41 • MIS Example Non-degenerate global minimum (MIS) 27-fold degenerate local minimum Degenerate local minima Global minimum M. H. S. Amin and V. Choi, PRA 80, 062326 (2009) • 42 • MIS Example ≡ WMIS (b) • 43 • Weighted MIS Wi = W Wi = 1 ∆ = 1 J = 2 • 44 • Spectral Gap W = 1.8 λ0 1 • 45 • Two Interesting Quantities Magnetization (as an order parameter): Spread of the wave-function: ∑ = = m i i m 1 0 1ψ N mS 2 = S = fraction of states participating in the superposition • 46 • Order Parameter & Wave Function Spread W = 1.8 • 47 • Minimum Gap ∆U ∆U = 4(2−W)      0Barrier height ∆E = 12(2−W)      0 as W 2 ∆E • 48 • Minimum Gap ∆U = 4(2−W)      0Barrier height ∆E = 12(2−W)      0 as W 2 The gap is exponentially sensitive to W • 49 • 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) . . . Quantum Annealing With Superconducting Qubits Mohammad Amin D-Wave Systems Inc. • 2 • Basic Circuit Elements C QCVE 22 1 22 == L LIE 22 1 22 Φ == φcosJEE −= Capacitance: Inductance: Josephson junction: Q Φ φ • 3 • RF-SQUID φcos 22 22 JELC QE −Φ+=QΦ φ • 4 • RF-SQUID φcos 22 22 JELC QE −Φ+= Flux quantization: Q Φ φ 0 2 Φ Φ = piφ Faraday’s law: C QV ==Φ& 0 2 2 2cos 2 )(           ),( 2 1 Φ Φ − Φ =ΦΦ+Φ= piJEL VVCE & )( 2 1 2 xVxmE += &Newtonian mechanics: Kinetic energy Potential energymass • 5 • C QC 22 1 22 =Φ& Comparing RF-SQUID with a particle Φxposition )(xVPotential energy particle SQUID Cmmass CVCQ =Φ= &xmp &=momentum m p xm 22 1 22 =&kinetic energy hipx =],[commutators hiQ =Φ ],[ )(ΦV • 6 • RF-SQUID Hamiltonian 0 2 2 2 cos 2 )()( )( 2 Φ Φ − Φ−Φ =Φ Φ+= pi J x E L V V C QH QΦ φ xΦ • 7 • RF-SQUID Hamiltonian 0 2 2 2 cos 2 )()( )( 2 Φ Φ − Φ−Φ =Φ Φ+= pi J x E L V V C QH QΦ φ xΦ Φ )(ΦV 0 1 02 1 Φ≈Φ x 0 1 [ ]xzH σεσ ∆+−≈ 2 1 ∆ tunneling amplitude • 8 • CJJ RF-SQUID Qubit δU ε Φ1x controls energy bias ε Φ2x controls barrier height δU Control knobs: 0 1 [ ]xz UH σδεσ )(2 1 ∆+−= • 9 • Actual Qubit Inductance tuner Readout Junction asymmetry compensator Ip compensator Harris et al, arXiv:1004.1628 (2010) • 10 • Programmable Magnetic Memory (PMM) Johnson et al., Supercond. Sci. Technol. 23, 065004 (2010) • 11 • Fabrication • 12 • Eight-Qubit Unit Cell Qubit #1 • 13 • 128 Qubits Chip • 14 • Wire Bounded Chip • 15 • Pulse Tube Dilution Refrigerator • 16 • 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 ε εε • 17 • Annealing in Our Hardware Hamiltonian:       Γ−= ∑ = N i x iP tHtEH 1 )()( σ ∑ ∑ = = += N i N ji z j z iij z iiP JhH 1 1, σσσ E(t) changes from 0 to Emax:   Classical annealing! )(2 )()( tE t t ∆ =Γ Γ(t) changed from Γmax to 0:   Quantum annealing! • 18 • Is it quantum or classical annealing? Question: It depends on which one of quantum or thermal fluctuations are stronger Answer: How can we determine this experimentally? • 19 • ICurrent biased Josephson junction: φ φ U )/exp()2/( TkU Bp ∆−=Γ piω Classical escape rate: Quantum escape (tunneling) rate: T oft independen =Γ ∆U Macroscopic Quantum Tunneling • 20 • Classical prediction Saturation due to quantum tunneling • 21 • Classical Annealing tfreeze Time Dynamics No Dynamics number small  )/exp()2/( =∆−=Γ TkU Bfreezep piω TUtU freezefreeze ∝∆=∆ )(Therefore: TtttU freeze ∝∝∆                      )(If                 then very similar to Tesc • 22 • Therefore                                  or Quantum Annealing indepdent −=Γ T tindependen −= Tt freeze Tunneling No Tunneling tfreeze Quantum mechanically tunneling amplitude exponentially depends on  ∆U but not  T Time • 23 • h-Ramping Experiment xz tthtE H σσ )()()( Γ−= t h(t) h0 tfreezetd If td  < tfreeze then the final probability is: P0(h=h0) > 0.5 • 24 • h-Ramping Experiment t h(t) h0xz tthtE H σσ )()()( Γ−= If td  > tfreeze then the final probability is: P0(h=0) = 0.5 If td  < tfreeze then the final probability is: P0(h=h0) > 0.5 tfreeze td P0(td) tfreeze 0.5 td • 25 • Single-Qubit Data td [µs] P0(td) tfreeze P0(td) Quantum Simulations td [µs] Experimental Data 40.00% 50.00% 60.00% 70.00% 80.00% 90.00% 100.00% 60 65 70 75 80 85 90 95 100 Classical Simulations P0(td) td [µs] 20 mK 50 mK 90 mK Temperature is measured independently using MRT 0 • 26 • Freeze-out Time Freeze-out time measurement Devoret et al., PRL (1985) Classical prediction Saturation due to quantum tunneling • 27 • Experiment vs. Simulations 2-state modeling 4-state modeling All simulations are done with no fitting parameter • 28 • 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 • 29 • Can we do this for more than one qubit? • 30 • 8-Qubit Ferromagnetic Chain ∑ ∑ = = −= N i N ji z j z i z iiP JhH 1 1, σσσ Hamiltonian: ∑Γ−= i x iP tHtE H σ)()( • 31 • 8-Qubit Ferromagnetic Chain Domain wall can be in any of the 7 sites with probability 1/7 • 32 • 8-Qubit Ferromagnetic Chain h << J Domain wall most probably on the right site • 33 • 8-Qubit Ferromagnetic Chain Ground state h << J • 34 • Question: Is the ground state reached via classical or quantum annealing? • 35 • 8-Qubit h-Ramping Experiment ∑Γ−= i x iP thHtE H σ)()()( td  < tfreeze P0(h=h0) > 1/7 t h(t) h0 tfreezetd h << J • 36 • 8-Qubit h-Ramping Experiment ∑Γ−= i x iP thHtE H σ)()()( td  < tfreeze P0(h=h0) > 1/7 td  > tfreeze P0(h=0) = 1/7 t h(t) h0 tfreeze td h << J • 37 • 8-Qubit h-Ramping Experiment ∑Γ−= i x iP thHtE H σ)()()( td  < tfreeze P0(h=h0) > 1/7 td  > tfreeze P0(h=0) = 1/7 td P0(td) tfreeze 1/7 h << J • 38 • 0 8-Qubit Experimental Results Saturation of the freeze-out time cannot be explained by classical physics P0(td) • 39 • Modeling The System Write down a Hamiltonian and solve it both Classically: Using Langevin equation Quantum Mechanically: Using density matrix approach • 40 • RF-SQUID Hamiltonian Hamiltonian: Interaction with environment: Noise spectral density: All parameters, including noise, are determined via independent experiments • 41 • Extracting Noise Parameters ε Γ(ε) η is extracted from measuring the Macroscopic Resonant Tunneling (MRT) A is determined from 1/f noise measurement • 42 • Extracting Noise Parameters • 43 • Classical Modeling Langevin equation: Fluctuation dissipation theorem: Force NoiseDissipation 0 12 Φ Φ = pix dx dU xF −=)( • 44 • 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) • 45 • Quantum Modeling Quantum mechanically energy is quantized Qubit Model: Keep lowest 2 energy levels Qudit Model: Keep lowest d energy levels • 46 • 4-Level Qudit Model 10 00 01 11 All levels within each well are logically equivalent Logical 0 Logical 1 00 Logical qubitAncilla qubit • 47 • Qubit Representation of Qudits XZ coupling XX coupling • 48 • Multi-Qubit System • 49 • Multi-Qubit System Couple to each qubit an ancilla qubit with XX+XZ coupling • 50 • Multi-Qubit System Original qubit Hamiltonian Interaction Hamiltonian: Coupled system Hamiltonian: The final ground state is unaffected by ancilla qubits All parameters are directly extracted from the rf-SQUID Hamiltonian • 51 • Experiment vs. Simulations Single Qubit8 Qubit Chain Classical and quantum simulations agree with experiment with no free parameters • 52 • Collaborators: Experiment: A.J. Berkley, E. Chapple, S. Gildert, R. Harris, J. Johansson, M.W. Johnson, T. Lanting, B. Wilson Simulations: N. Dickson, F. Hamze, K. Karimi, C. Truncik 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`

#### 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}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
```
``` Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
`https://iiif.library.ubc.ca/presentation/dsp.59370.1-0040933/manifest`