Discrete Optimisation Problems on Adiabatic Quantum Computer
Explore the world of adiabatic quantum computing with insights on discrete optimisation problems, hardware limitations, and the working principles of an adiabatic quantum computer. Learn about solver for quadratic unconstrained binary optimisation problems, measurement in quantum physics, and more.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
DLR.de Chart 1 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Discrete optimisation problems on an adiabatic quantum computer Tobias Stollenwerk, Elisabeth Lobe, Anke Tr ltzsch Simulation and Software Technology German Aerospace Center (DLR) BFG 2015, London, 16.6.2015
DLR.de Chart 2 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Outlook Introduction to Adiabatic Quantum Computing Hardware limitations Application: Clique Problem
DLR.de Chart 3 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 What is an Adiabatic Quantum Computer? Solver for Quadratic Unconstraind Binary Optimisation Problems (QUBOs) ?(?1,?2, , ??) = ????? + ????????? with ?? 0,1 On-site strength ?? Coupling ??? Source: D-Wave Sys. Device by company D-Wave Systems commercially available We have access to hardware simulator / programming interface
DLR.de Chart 4 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Quantum physics Eigenvalue equation determines physical state of a system ? | ?? = ??| ?? ?? Hilbert space and ? is the where ??is the energy of the state and | Hamilton operator. Discrete Eigenvalues lead to quantised energy levels. Energy ?3 ?2 ?1
DLR.de Chart 5 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Measurement in Quantum physics Let the system be in a superposition of energy Eigen states | ?? | ? = ??| ?? ? Measurement of energy ?? changes state | ? ?? ?? |? = ?? |?? Probability ?j to measure state |?? 2 ??= ??
DLR.de Chart 6 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Adiabatic Quantum Computer How does it work? Encode objective function in ground state of quantum system Initial system groundstate simple and implementable Energy levels Energy Fast transition Initial system Final system Time
DLR.de Chart 7 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Adiabatic Quantum Computer How does it work? Sufficiently slow (adiabatic) transition to final system Lowest energy gap ? determines runtime Energy levels Energy ? Slow transition Initial system Final system Time
DLR.de Chart 8 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Quantum Bits Two Level Quantum Systems Classical bits Quantumbits (Qubits) Voltage State is Superposition of 0 und 1 | ? = ?| 0 + ?| 1 1 Measurement changes the state Observe 0 with probability ?2 | ? = | Observe 1 with probability ?2 | ? = | 0 0 1 Multiple Qubits | ? 12 = ?2 ?1 | e.g. | ?12 = 12 01 |
DLR.de Chart 9 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Adiabatic Optimisation Procedure 0 0 1 0 1 1 0 0 1 0 1 1 0 1 0 1 0 1 Solution All qubits in mixed state 0 = 1 1 = 1 2 0 + 1 ) 1 Farhi et. al., Quantum Computation by Adiabatic Evolution (2001)
DLR.de Chart 10 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Why use an Adiabatic Quantum Computer? QUBO / Ising is NP-hard Quantum speed-up assumed but subject to discussion (Defining and detecting quantum speedup, R nnow et. al., Science 345, 1695, (2014)) Map other NP-hard problems to QUBO/Ising (Ising Formulations of many NP problems, A. Lucas, Frontiers in Physics (2014))
DLR.de Chart 11 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Hardware limitations on a D-Wave device ?? Unit cell with 8 Qubits an 2 partitions 8x8 Unit cells on D-Wave On chip 512 Qubits ??? Range of strenghts ?? and couplings ??? limited and subject to uncertainties
DLR.de Chart 12 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Hardware limitations on a D-Wave device Not all Qubits are connected How to realise complete graphs? Solution: Connection via other qubits Representation of a logical qubit with several physical qubits
DLR.de Chart 13 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Overcome connectivity limitation Rule for implementing a complete graph onto the D-Wave hardware: Source: D-Wave Sys. Simulator Software Documentation
DLR.de Chart 14 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Maximum Clique problem - Example 1 Find largest complete subgraph 2 3 4 5 7 8 9 6 10
DLR.de Chart 15 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Maximum Clique problem - Example 2 3 1 4 10 5 6 9 7 8
DLR.de Chart 16 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Clique problem as QUBO ? ? Set negative strength at all nodes, e.g. ??= 1 2 3 ??= ? +10 1 4 Penalise all edges of graph complement with positive couplings, e.g. ???= +10 5 10 Edges of the graph itself can be activated without penalty, ? 6 9 ? ? 7 8 ?(?1,?2, , ??) = ????? + ????????? ? ?
DLR.de Chart 17 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Cliquen Problem on D-Wave Device 1 logical qubit 4 physical qubits 5 5 5 5 -7 -7 -7 -1 1 2 3 4 5 6 7 8 9 10
DLR.de Chart 20 > Discrete optimisation problems on an adiabatic quantum computer > T. Stollenwerk, E. Lobe, A. Tr ltzsch > 16.6.2015 Outlook What kind of problems can be converted to QUBO? Combine conventional algorithms with AQC (hybrid approach) Investigate scaling behaviour
