Embedding Logical Qubits into the D-Wave Hardware Graph Keith Britt [email protected] February 26th, 2014 Agenda • • • • • • • • A Little Bit About Quantum Computing A Little Bit About D-Wave The D-Wave Hardware Transforming the Hardware into a Graph Embedding Literature “Review” Embedding Limits Example Embedding(s) Homework Problems Quantum Computing • In the Quantum World, classical physics give way to 2 phenomena: – Superposition – Entanglement • We can use these phenomena to massively parallelize computation and also do some crazy stuff that is otherwise impossible (truly random numbers, data teleportation, etc.) Quantum Computing • Parallelism Scales Exponentially with the Number of Qubits (2 ) • Several Models of Quantum Computation – Gate/Circuit Model – Adiabatic Model – Topological model (and more…) • The First Commercially Available Quantum Computer (D-Wave) Uses the Adiabatic Model D-Wave • Canadian Company Founded by Physicists and Material Scientists • Created a Quantum Chip Using Adiabatic Model Running at Extremely Cold Temperatures and Minimal Interference • Very Controversial… Is the Computer Really Quantum? Is It Worth It? – Simulations Beat It – Classical Adiabatic Computer Matched It Ising Model = , + , ∈ ℎ : : ℎ : , : : ℎ ∈ State (Spin/Value) of the Qubit ( −1, 1 0, 1 ) Set of Qubits Strength of the Qubit Value Strength of the Qubit-Qubit Interaction The Total Energy of the System http://dwave.files.wordpress.com/2010/12/weightedmaxsat_v2.pdf D-Wave Hardware http://dwave.wordpress.com/2011/12/01/vesuvius-a-closer-look-512-qubit-processor-gallery/ So is Hardware Just a Line Graph? Not Valid Unit Cell Graph Representation • Each Qubit Becomes a Vertex • Each Coupler Becomes an Edge Between Vertices Valid Ising Model = , + , ∈ ℎ Edge Weights : : ℎ : , : : ℎ ∈ Vertex Weights State (Spin/Value) of the Qubit ( −1, 1 0, 1 ) Set of Qubits Strength of the Qubit Value Strength of the Qubit-Qubit Interaction The Total Energy of the System http://dwave.files.wordpress.com/2010/12/weightedmaxsat_v2.pdf Linking Unit Cells Linking Unit Cells Not Valid Linking Unit Cells Valid • 512 Vertices (Qubits) • 16 Intra Unit Cell Edges per Unit Cell • 8 – 16 Inter Unit Cell Edges per Unit Cell Literature Review • Choi, Vicky. Minor-Embedding in Adiabatic Quantum Computation: I. The Parameter Setting Problem. Quantum Information Processing, 7, pp 193 – 209, 2008. arXiv:0804.4884v1 [quant-ph]. • Choi, Vicky. Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design. Quantum Information Processing: Volume 10, Issue 3 (2011), Page 343. arXiv:1001.3116v2 [quant-ph]. • Klymko, C., Sullivan, B., Humble, T. Adiabatic quantum programming: minor embedding with hard faults. Quantum Information Processing: Volume 13, Issue 3 (2014), pp 709 – 729. arXiv:1210.8395v2 [quant-ph]. D-Wave Embedding Limits • Logical Qubit is Not the Same as a Physical Qubit • Can Always Embed N Logical Qubits onto 2 Physical Qubits • This is Not a Tight Upper-bound, Even for Complete Graphs • Choi’s Triad Technique Able to Embed 17 on 128-Qubit Processor (17 > 128) Logical to Physical • A Logical Qubit can be Spread Over Multiple Physical Qubits as Long as There is a Common Path Between All The Physical Qubits NOT VALID VALID Something We’re Not Going Over = , + , ∈ ℎ Edge Weights ℎ ∈ Vertex Weights , and ℎ values determine a lot about how aligned qubits are with one another. This gets a bit too outside of graph theory, but there’s an easy to read explanation at: http://www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.pdf An Example • Embed 4 into a Unit Cell http://arxiv.org/pdf/1001.3116v2.pdf http://arxiv.org/pdf/1001.3116v2.pdf Embedding 8 • Start by Embedding 4 in a Unit Cell Embedding 8 • Next Embed the Other 4 in a Unit Cell Embedding 8 • Next Embed 4,4 in a Unit Cell Embedding 8 • Tada! 8 is embedded in the D-Wave Hardware Homework Questions • Embed 12 into the D-Wave Hardware Graph in 6 or Fewer Unit Cells. Homework Questions • Embed the Peterson Graph into the D-Wave Hardware Graph (Diamond Isomorphism) in 6 or Fewer Unit Cells.