Adiabatic Quantum Computing

Quantum Effects are Everywhere

Optical interference effects are quantum effects

Iridescence in Roman Glass

Anti-Reflective Coatings

Quantum Effects are Everywhere

Wave effects are quantum effects:

Lasers show wave phenomena.

Many more examples at my old lecture notes.

Quantum Computing

Probabilistic computing - superposition and entanglement

​

Quantum Computing

Quantum Binary Digits - qubits

​

Quantum Computing Collapse

Quantum Decoherence: waves "collapse" when you "observe" them.

• Either some unexplained phenomenon censors macroscopic waves,
• or the wave superposition gets extended to the observer too.

Preventing unintended decoherence is the central engineering challenge to scaling quantum computers.

​

Quantum Computing Overview

Put inputs into superposition of 0 and 1 - like a SAT variable

Perform reversible quantum gate computations, like controlled NOT - limits answers like SAT clauses

Collapse on a probabilistic answer - like a SAT solver with multiple solutions

​

​

History of Quantum Computing

• 1994 - Shor Factoring algorithm
• Factors numbers in polynomial time (breaking RSA) on general quantum computer
• 2001 - IBM Factors 15
• 7-qubit Nuclear Magnetic Resonance Computer
• Did not do entanglement
• 2009 - Quantum Optics University of Bristol
• All-optical quantum gate (but only one gate!)
• 2011 - D-Wave Quantum Annealer
• Adiabatic model Quantum Computer
• Built on a scalable semiconductor process
• 2011 - Proof of Quantum Von Neumann ( RAM Separation )
• 2011 - 143 factored using only 4 qubits
• 2012 - 1QBit first quantum software company in Vancouver

General Purpose Quantum Computer

Quantum Computer (QC) - a type of analog computer that uses quantum mechanics to solve problems

Universal Quantum Computer - uses quantum logic gates, can implement any function

Quantum logic gates - reversible (linear) operators. Number of outputs must equal number of inputs to be reversible.

Limitations:

• No-cloning theorem means you can't copy a qubit (no assignments)

Adiabatic Quantum Computer

Adiabatic - occurring without gain or loss of heat

Adiabatic Quantum Computer - subset of quantum computing that exploits the adiabatic theorem

Adiabatic Theorem

• The Adiabatic Theorem
• Start in ground state*
• Adiabatically* increase the cost function
• Guaranteed* to still be in ground state
• Ground state
• == global minimum of the energy function
• == absolute zero
• *Limitations
• Real systems have noise
• So it's impossible to guarantee we start in the ground state (exactly at absolute zero)
• It's also impossible to implement perfectly adiabatic cost changes in finite time
• Mathematical guarantee only, real systems will have errors depending on noise
• Benefits: real quantum speedup, zero energy consumption

Quantum Annealing

• Simulated Annealing problem
• Done with classical computation
• or Adiabatic Quantum Computer
• Find a global minimum of function

​

• Intuition: quantum tunneling lets solution escape a local minimum

Quantum Adiabatic Algorithm

Proposed by Farhi et al

1. Take a difficult (classical) optimization problem
2. Encode its solution in the ground state of a quantum “problem Hamiltonian" (an operator that tells you the total system energy)
3. Map the problem Hamiltonian to the hardware circuits (including error correction)
4. Prepare the system in the ground state of another easily solvable “drive” Hamiltonian (usually the identity, where the ground state is all zeros)
5. Vary the Hamiltonian slowly and smoothly until it matches the problem Hamiltonian. Still in ground state, due to adiabatic theorem.
6. Collapse the system and read off the (probabilistic) answer

D-Wave

• Canadian Company that produces Adiabatic Quantum Computers
• 2011 Lockheed purchased 128-qubit processor
• 2013 Google purchased 512-qubit processor
• 2017 D-Wave released 2048-qubit processor
• 2019 D-Wave sells 5000-qubit processor to Los Alamos National Lab
• ​
• Researchers have showed promising results on a variety of problems, but achieving "quantum supremacy" (truly faster than any classical machine) is still limited to specialized toy examples rather than real-world problems.

​

Why Adiabatic?

For 25+ years, people have tried to build scalable universal quantum computers. IBM is currently at 50 qubits, but even at 5 qubits, gate error rate is several percent. Google is at 72 qubits, barely under 1% error rate, getting useful results with 53 qubit machines. Intel is at 49 qubits, is working on tiny spin qubits, and expects production-level systems in "ten years" (AKA, after solving many problems).

D-Wave is shipping scalable adiabatic quantum computers with 2000 qubits today, and building 5000 qubit machines.

The Central Challenge: Writing Quantum Software

• QMASM: circuit-level assembler for D-Wave's adiabatic quantum machines.
• OpenQASM: gate-level assembler for IBM's Q Experience
• QCL: basically C with "qureg" type and quantum operators.
• Q#: Microsoft's functional language for quantum computing
• Quipper: a Haskell-based functional language targeting general purpose quantum machines, that can synthesize reversible quantum circuits.

​

​