Report

Optimization Algorithms on a Quantum Computer A New Paradigm for Technical Computing Richard H. Warren, PhD [email protected] © Copyright 2011 Lockheed Martin Corporation 1 Lockheed Martin Buys Quantum Computer In 2011 Lockheed Martin Corp. purchased a quantum computer from D-Wave Systems, a Canadian technology firm. 2 Lockheed Martin Buys Quantum Computer In 2011 Lockheed Martin Corp. purchased a quantum computer from D-Wave Systems, a Canadian technology firm. Lockheed Martin planned uses: • software validation and verification methods 3 Lockheed Martin Buys Quantum Computer In 2011 Lockheed Martin Corp. purchased a quantum computer from D-Wave Systems, a Canadian technology firm. Lockheed Martin planned uses: • software validation and verification methods • complex systems engineering 4 Lockheed Martin Buys Quantum Computer In 2011 Lockheed Martin Corp. purchased a quantum computer from D-Wave Systems, a Canadian technology firm. Lockheed Martin planned uses: • software validation and verification methods • complex systems engineering • algorithms and computer science 5 Lockheed Martin Buys Quantum Computer In 2011 Lockheed Martin Corp. purchased a quantum computer from D-Wave Systems, a Canadian technology firm. Lockheed Martin planned uses: • software validation and verification methods • complex systems engineering • algorithms and computer science • enhanced machine learning 6 Ising Function for Quantum Annealing Quantum bits (qubits) can achieve an optimal state of low energy when super cooled. i and j are qubits 7 Ising Function for Quantum Annealing Quantum bits (qubits) can achieve an optimal state of low energy when super cooled. i and j are qubits Inputs: hi = the energy bias for qubit i Jij = the coupling energy between qubits i, j 8 Ising Function for Quantum Annealing Quantum bits (qubits) can achieve an optimal state of low energy when super cooled. i and j are qubits Inputs: hi = the energy bias for qubit i Jij = the coupling energy between qubits i, j Output: si = the state of qubit i, either 0 or 1 9 Quantum Machine Hardware • Qubit is a loop of superconducting wire made of niobium 10 Quantum Machine Hardware • Qubit is a loop of superconducting wire • Coupling between qubits is magnetic wiring 11 Quantum Machine Hardware • Qubit is a loop of superconducting wire • Coupling between qubits is magnetic wiring • Temperature is close to 0 degrees kelvin 12 Quantum Machine Hardware • • • • Qubit is a loop of superconducting wire Coupling between qubits is magnetic wiring Temperature is close to 0 degrees kelvin Quantum machine has 128 qubits arranged in blocks of 8 qubits. All qubits in a block are coupled. Limited coupling between qubits in different blocks. 32 qubits were inoperative. – Result: Maximum number of qubits that can be logically coupled is 13 13 Adiabatic Quantum Optimization • Physics inspired approach • Hamiltonian changes over time – After the computation is complete • Non-zero probability the system is in its lowest energy state which encodes a global minimization of the problem being solved 14 Programming Minimization Problem 1. Convert variables to binary 0, 1 15 Programming Minimization Problem 1. Convert variables to binary 0, 1 2. Design objective function 16 Programming Minimization Problem 1. Convert variables to binary 0, 1 2. Design objective function 3. Convert constraints to penalty functions 17 Programming Minimization Problem 1. 2. 3. 4. Convert variables to binary 0, 1 Design objective function Convert constraints to penalty functions Combine object function & penalty functions into one expression that has only linear and quadratic terms 18 Programming Minimization Problem 1. 2. 3. 4. Convert variables to binary 0, 1 Design objective function Convert constraints to penalty functions Combine object function & penalty functions into one expression that has only linear and quadratic terms 5. Map #4 to quantum machine hardware 19 Programming Minimization Problem 1. 2. 3. 4. Convert variables to binary 0, 1 Design objective function Convert constraints to penalty functions Combine object function & penalty functions into one expression that has only linear and quadratic terms 5. Map #3 to quantum machine hardware 6. Interface to quantum machine through processor, such as MATLAB or Python 20 Programming Minimization Problem (cont’d) • si are the variables – Hardware limited to 13 fully coupled variables • Hamiltonian = at most 13 X 13 matrix for full coupling – Diagonal elements are hi – Off diagonal elements are Jij 21 Symmetric Traveling Salesman Problem (TSP) A salesman needs to visit n cities once and return to the starting city. The distance dij between each pair of cities i, j is know. Symmetric means dij = dji What is a route that minimizes the distance that the salesman travels? 22 Symmetric Traveling Salesman Problem (TSP) A salesman needs to visit n cities once and return to the starting city. The distance dij between each pair of cities i, j is know. Symmetric means dij = dji What is a route that minimizes the distance that the salesman travels? Our binary variables are xij for the road from city i to city j for i < j. The number of variables is n(n – 1)/2 which is 10 for 5 cities and 15 for 6 cities. 23 Symmetric Traveling Salesman Problem (TSP) A salesman needs to visit n cities once and return to the starting city. The distance dij between each pair of cities i, j is know. Symmetric means dij = dji What is a route that minimizes the distance that the salesman travels? Our binary variables are xij for the road from city i to city j for i < j. The number of variables is n(n – 1)/2 which is 10 for 5 cities and 15 for 6 cities. Our objective function is Σdijxij for i < j. 24 Symmetric Traveling Salesman Problem (TSP) A salesman needs to visit n cities once and return to the starting city. The distance dij between each pair of cities i, j is know. Symmetric means dij = dji What is a route that minimizes the distance that the salesman travels? Our binary variables are xij for the road from city i to city j for i < j. The number of variables is n(n – 1)/2 which is 10 for 5 cities and 15 for 6 cities. Our objective function is Σdijxij for i < j. The constraints are xij = xji , xij2 = xij and constraints to ensure the salesman uses exactly 2 roads for each city, one into the city and different one out of the city. For city 1 in a 4 city problem, our constraint is C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 25 Constraint C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 ensures one route into city 1 and one route out of city 1 • None of the routes x12, x13, x14 are selected Then C(x12, x13, x14) = (0 + 0 + 0 - 2)2 = 4 26 Constraint C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 ensures 1 route into city 1 and 1 route out of city 1 • None of the routes x12, x13, x14 are selected Then C(x12, x13, x14) = (0 + 0 + 0 - 2)2 = 4 • One of the routes is selected, say x12 Then C(x12, x13, x14) = (1 + 0 + 0 - 2)2 = 1 27 Constraint C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 ensures 1 route into city 1 and 1 route out of city 1 • None of the routes x12, x13, x14 are selected Then C(x12, x13, x14) = (0 + 0 + 0 - 2)2 = 4 • One of the routes is selected, say x12 Then C(x12, x13, x14) = (1 + 0 + 0 - 2)2 = 1 • Two of the routes are selected, say x12 and x13 Then C(x12, x13, x14) = (1 + 1 + 0 - 2)2 = 0 28 Constraint C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 ensures 1 route into city 1 and 1 route out of city 1 • None of the routes x12, x13, x14 are selected Then C(x12, x13, x14) = (0 + 0 + 0 - 2)2 = 4 • One of the routes is selected, say x12 Then C(x12, x13, x14) = (1 + 0 + 0 - 2)2 = 1 • Two of the routes are selected, say x12 and x13 Then C(x12, x13, x14) = (1 + 1 + 0 - 2)2 = 0 • All three of the routes are selected Then C(x12, x13, x14) = (1 + 1 + 1 - 2)2 = 1 29 Ensuring result is a tour for 4 city TSP Case for city 1 use C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 • Consider solution (x12 x21) and (x34 x43) Then C(x12, x13, x14) = (1 + 0 + 0 - 2)2 = 1 30 Ensuring result is a tour for 4 city TSP Case for city 1 use C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 • Consider solution (x12 x21) and (x34 x43) Then C(x12, x13, x14) = (1 + 0 + 0 - 2)2 = 1 • Consider solution (x23 x34 x42) Then C(x12, x13, x14) = (0 + 0 + 0 - 2)2 = 4 31 Ensuring result is a tour for 4 city TSP Case for city 1 use C(x12, x13, x14) = (x12 + x13 + x14 – 2)2 • Consider solution (x12 x21) and (x34 x43) Then C(x12, x13, x14) = (1 + 0 + 0 - 2)2 = 1 • Consider solution (x23 x34 x42) Then C(x12, x13, x14) = (0 + 0 + 0 - 2)2 = 4 • Consider solution (x12 x23 x34 x41) Then C(x12, x13, x14) = (1 + 0 + 1 - 2)2 = 0 32 Compute Hamiltonian for 4 City TSP Step 1: Reduce constraint function for each city For city 1: Let a = x12 , b = x13 and c = x14 Then (x12 + x13 + x14 – 2)2 = a2 + b2 + c2 + 2(ab + bc + ac) – 4(a + b + c) + 4 Applying a2 = a, b2 = b and c2 = c Then (x12 + x13 + x14 – 2)2 = 2(ab + bc + ac) – 3(a + b + c) + 4 33 Compute Hamiltonian for 4 City TSP Step 1: Reduce constraint function for each city For city 1: Let a = x12 , b = x13 and c = x14 Then (x12 + x13 + x14 – 2)2 = a2 + b2 + c2 + 2(ab + bc + ac) – 4(a + b + c) + 4 Applying a2 = a, b2 = b and c2 = c Then (x12 + x13 + x14 – 2)2 = 2(ab + bc + ac) – 3(a + b + c) +4 Step 2: Add coefficients of linear terms to diagonal Add coefficients of quadratic terms to off diagonal 34 Compute Hamiltonian for 4 City TSP Step 1: Reduce constraint function for each city For city 1: Let a = x12 , b = x13 and c = x14 Then (x12 + x13 + x14 – 2)2 = a2 + b2 + c2 + 2(ab + bc + ac) – 4(a + b + c) + 4 Applying a2 = a, b2 = b and c2 = c Then (x12 + x13 + x14 – 2)2 = 2(ab + bc + ac) – 3(a + b + c) +4 Step 2: Add coefficients of linear terms to diagonal Add coefficients of quadratic terms to off diagonal Step 3: Add coefficients of objective function Σdijxij to diagonal 35 Compute Hamiltonian for 4 City TSP Step 1: Reduce constraint function for each city For city 1: Let a = x12 , b = x13 and c = x14 Then (x12 + x13 + x14 – 2)2 = a2 + b2 + c2 + 2(ab + bc + ac) – 4(a + b + c) + 4 Applying a2 = a, b2 = b and c2 = c Then (x12 + x13 + x14 – 2)2 = 2(ab + bc + ac) – 3(a + b + c) +4 Step 2: Add coefficients of linear terms to diagonal Add coefficients of quadratic terms to off diagonal Step 3: Add coefficients of objective function Σdijxij to diagonal Hamiltonian is input to quantum computer 36 Job Shop Problem on One Processor There are n jobs. Each job has an earliest time it can be started, latest time it can be finished, length of time to complete it, and setup time to prepare processor. The number of start times is small. A value vj is assigned for completing job j. Maximize the value by completing jobs. 37 Job Shop Problem on One Processor There are n jobs. Each job has an earliest time it can be started, latest time it can be finished, length of time to complete it, and setup time to prepare processor. The number of start times is small. A value vj is assigned for completing job j. Maximize the value by completing jobs. Our binary variables are xjt where j designates a job and t designates a start time for job j. 38 Job Shop Problem on One Processor There are n jobs. Each job has an earliest time it can be started, latest time it can be finished, length of time to complete it, and setup time to prepare processor. The number of start times is small. A value vj is assigned for completing job j. Maximize the value by completing jobs. Our binary variables are xjt where j designates a job and t designates a start time for job j. Our objective function is -Σvjxjt over all jobs j and all start times t for job j. 39 Job Shop Problem on One Processor There are n jobs. Each job has an earliest time it can be started, latest time it can be finished, length of time to complete it, and setup time to prepare processor. The number of start times is small. A value vj is assigned for completing job j. Maximize the value by completing jobs. Our binary variables are xjt where j designates a job and t designates a start time for job j. Our objective function is -Σvjxjt over all jobs j and all start times t for job j. Constraints model: At most one job can start at time t A job can start at most once Two jobs cannot be running at the same time. 40 Job Shop Problem on One Processor There are n jobs. Each job has an earliest time it can be started, latest time it can be finished, length of time to complete it, and setup time to prepare processor. The number of start times is small. A value vj is assigned for completing job j. Maximize the value by completing jobs. Our binary variables are xjt where j designates a job and t designates a start time for job j. Our objective function is -Σvjxjt over all jobs j and all start times t for job j. Constraints model: At most one job can start at time t A job can start at most once Two jobs cannot be running at the same time. Constraints introduce new variables that limit job variables xjt to 7 for quantum processor. These are slack variables similar to those in linear programming. 41 Other Inputs to Quantum Processor • LaGrange multipliers – balance objective function and constraints. Very sensitive. 42 Other Inputs to Quantum Processor • LaGrange multipliers – balance objective function and constraints. Very sensitive. • Cooling time – time to allow processor to reach near 0 degrees kelvin 43 Other Inputs to Quantum Processor • LaGrange multipliers – balance objective function and constraints. Very sensitive. • Cooling time – time to allow processor to reach near 0 degrees kelvin • Annealing time – time to allow processor to reach minimum energy state, after cooled 44 Other Inputs to Quantum Processor • LaGrange multipliers – balance objective function and constraints. Very sensitive. • Cooling time – time to allow processor to reach near 0 degrees kelvin • Annealing time – time to allow processor to reach minimum energy state, after cooled • Iterations – number of times same problem is sampled. We found optimal 99% of time for 100 iterations of 4 city TSP. 45 Other Inputs to Quantum Processor • LaGrange multipliers – balance objective function and constraints. Very sensitive. • Cooling time – time to allow processor to reach near 0 degrees kelvin • Annealing time – time to allow processor to reach minimum energy state, after cooled • Iterations – number of times same problem is sampled. We found optimal 99% of time for 100 iterations of 4 city TSP. • Loads – number of times to iterate 46 Advantage of Quantum Annealing • Speed of solving intractable problems – Experimental evidence shows several orders of magnitude faster than current digital computers – Not known whether polynomial or exponential 47 Limitations of Quantum Annealing • Limited number of qubits restricts number of variables hi • Limited connectivity between qubits restricts which parameters Jij can be nonzero • Precision affected by temperature and analog nature of parameters hi and Jij in hardware Techniques Limitations Techniquesthat thatOvercome Mitigate Limitations 48 Comparison to Linear Programming Linear Programming • • • • • Optimization technique Linear objective function Variables ≥ 0 Linear constraints Solution - Simplex Method Quantum Computing • • • • • Optimization technique Quadratic objective function Variables are 0 or 1 Quadratic constraints Solution - Adiabatic Annealing 49 Comparison to Linear Programming Linear Programming • • • • • • Optimization technique Linear objective function Variables ≥ 0 Linear constraints Solution - Simplex Method Runs in polynomial time Quantum Computing • • • • • • Optimization technique Quadratic objective function Variables are 0 or 1 Quadratic constraints Solution - Adiabatic Annealing Extremely fast on intractable problems 50 Comparison to Linear Programming Linear Programming • • • • • • Optimization technique Linear objective function Variables ≥ 0 Linear constraints Solution - Simplex Method Runs in polynomial time • Optimal solution from 1 execution Quantum Computing • • • • • • Optimization technique Quadratic objective function Variables are 0 or 1 Quadratic constraints Solution - Adiabatic Annealing Extremely fast on intractable problems • Near optimal solution from many executions 51 References 1. D. Aharonov et al., Adiabatic quantum computation is equivalent to standard quantum computation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, 42-51, (2004). 2. G. A. Kochenberger et al., A unified modeling and solution framework for combinatorial optimization problems, OR Spectrum, 26, 237-250, (2004) 3. K. Karimi and 8 other D-Wave employees, Investigating the performance of an adiabatic quantum optimization processor, Quantum Information Processing, published on line, (2011) 52 Summary • Inputs to adiabatic quantum computer are integers that are interpreted as analog • Adiabatic quantum computer optimizes all solutions simultaneously • Output from adiabatic quantum computer is 0, 1 assignment to variables with extremely high probability of being a minimization 53 Terminology • Adiabatic – describes a process in which there is no loss or gain of heat • Quantum annealing – hardware is cooled to a very low temperature which approximates the minimum energy function in the Ising model 54