Quantum annealing is basically a way of using the intrinsic effects of quantum physics to help us find the minimum energy state of something and solve certain types of problems:
- Optimization: A problem where we search for the best configuration out of many different possible combinations. The reason we can use physics to solve optimization problems is that we can frame them as an ‘energy minimization problem’. As you may know, a fundamental part of physics is that everything is always trying to find its minimum energy state. Things go down hills, and hot things cool down over time, etc.
- Probabilistic sampling: It’s slightly different from optimization. Instead of trying to find the minimum energy state, we sample from many low-energy states and characterize the shape of our energy landscape. These samples give us information about what our model is like now and we can use them to improve our model over time.
In quantum annealing, we harness the natural evolution of quantum states. Although we don’t have any control over that evolution. So we set up the problem at the beginning, let quantum physics do its natural evolution, and the configuration at the end corresponds to the answer we are trying to find.
But in Gate Model Quantum Computing, we try to control and manipulate the evolution of that quantum state over time which is a lot more difficult because quantum systems are incredibly delicate to work with. But having that amount of control lets us solve a bigger class of problems.
This difference is the reason why it’s been possible to scale up quantum annealing processes to over 7000 qubits whereas in Gate Model Quantum Computing we’ve reached almost 400 qubits.
This company uses the quantum annealing method in their quantum computers. It provides “Leap” which is a real-time quantum computing cloud — service that virtualizes quantum computing for almost anyone with a computer and a broadband connection to use.
Leap allows anyone to sign up, giving them one minute of time each month. That might not sound like much, but a key advantage of quantum computing is solving problems in milliseconds. D-Wave estimates that each user’s free minute of quantum computing time should be enough to run between 400 and 4,000 jobs each month. If developers want more, the company will charge commercial users $2,000 for one hour of access each month.
D-Wave is also offering Ocean SDK which includes a suite of open-source Python tools on the D-Wave GitHub repository for solving hard problems with quantum computers.
Problem Definition
We have a set of 4 pumps that we can use to satisfy daily consumer demand for water.
Objective:
Constraints:
- Each pump needs to run at least once per day
- At any time, at most 3 pumps can run
- We need to satisfy the demand for the day
# Scenario
pumps = [0, 1, 2, 3]
times = [0, 1]
demand = 20
flow = [2, 7, 3, 8]
costs = [[36, 27],
[56, 65],
[48, 36],
[52, 16]]
We should formulate this problem as a Binary Quadratic Model (BQM). BQM is the native form the problems need to be formulated as, in order to run on a quantum computer.
- QUBO: Quadratic expression with 0/1 variables
- Ising: Quadratic expression with -1/+1 variables
The form of BQM is as follows:
We have linear and quadratic terms. On QPUs (Quantum Processing Units):
- Qubits: Linear terms
- Couplers connecting pairs of Qubits: Quadratic terms
What we can control are the coefficients of these linear and quadratic terms (a and b). These values will turn into voltages, currents, and magnetic fields to act on our qubits. We will choose values for aᵢ and bᵢⱼ to model our problem so that, when we minimize this expression, the minimum value will occur at our minimum cost.
The qᵢ and qⱼ in this expression are going to be 0 & 1 (binary variables) and the quantum computer will tell us which values these qᵢ and qⱼ should take. Should they equal 0 or should they equal 1 to obtain our desired minimum cost?
A BQM equation consists of two parts: Objective & Constraint(s). We need to combine the constraints and the objective of our problem into one expression. We’ll use Ocean to build them into BQM.
Our Binary Variables:
We assign a variable for each time/pump combination:
- Value 0 means we don’t use the pump at that time.
- Value 1 means we use the pump at that time.
# Build a variable for each pump
x = [[f'P{p}_AM', f'P{p}_PM'] for p in pumps]
0. Import packages
from dwave.system import DWaveSampler, EmbeddingComposite
from dimod import BinaryQuadraticModel# Initialize bqm as QUBO
bqm = BinaryQuadraticModel('BINARY')
To build our BQM, we start by creating a BinaryQuadraticModel object. This is where we decide whether to choose QUBO or Ising.
1. Objective
Words:
Minimize overall cost
Math:
Add up cost over all pumps and time slots:
The quantum computer will minimize this expression and give us back whether each of the x values should be 0 or 1 for the minimum cost:
- If the pump is used at a given time: 1 * (cost to run pump)
- If the pump is not used at a given time: 0 * (cost to run pump)
(This is where we use our binary variables.)
Code:
# Objective
for p in pumps:
for t in times:
bqm.add_variable(x[p][t], costs[p][t])
2. Constraint 1
Words:
Each pump runs at least once per day
Math:
Code:
# Constraint 1: Every pump runs at least once per day
for p in pumps:
c1 = [(x[p][t], 1) for t in times]
bqm.add_linear_inequality_constraint(
terms=c1,
lb= 1,
ub=len(times),
lagrange_multiplier=5,
label='c1_pump_'+str(p))
- The method of Lagrange multipliers is a simple and elegant method of finding the local minima or local maxima of a function subject to equality or inequality constraints. We calculate the LaGrange parameter by guess and check. This problem can be solved in the Constrained Quadratic Model (CQM) which handles all of that for us.
3. Constraint 2
Words:
At most 3 pumps run at a time
Math:
Code:
# Constraint 2: At most 3 pumps run per time slot
for t in times:
c2 = [(x[p][t], 1) for p in pumps]
bqm.add_linear_inequality_constraint(
terms=c2,
constant=-3,
lagrange_multiplier=1,
label='c2_time_'+str(t))
4. Constraint 3
Words:
Total flow satisfies daily demand
Math:
Code:
# Constraint 3: Satisfy the daily demand
c3 = [(x[p][t], flow[p])for t in times for p in pumps]
bqm.add_linear_equality_constraint(
terms=c3,
constant=-demand,
lagrange_multiplier=28)
The entire code:
from dwave.system import DWaveSampler, EmbeddingComposite
from dimod import BinaryQuadraticModel# Scenario
pumps = [0, 1, 2, 3]
times = [0, 1]
demand = 20
flow = [2, 7, 3, 8]
costs = [[36, 27],
[56, 65],
[48, 36],
[52, 16]]
# Build a variable for each pump
x = [[f'P{p}_AM', f'P{p}_PM'] for p in pumps]
# Initialize bqm
bqm = BinaryQuadraticModel('BINARY')
# Objective
for p in pumps:
for t in times:
bqm.add_variable(x[p][t], costs[p][t])
# Constraint 1: Every pump runs at least once per day
for p in pumps:
c1 = [(x[p][t], 1) for t in times]
bqm.add_linear_inequality_constraint(
terms=c1,
lb= 1,
ub=len(times),
lagrange_multiplier=5,
label='c1_pump_'+str(p))
# Constraint 2: At most 3 pumps run per time slot
for t in times:
c2 = [(x[p][t], 1) for p in pumps]
bqm.add_linear_inequality_constraint(
terms=c2,
constant=-3,
lagrange_multiplier=1,
label='c2_time_'+str(t))
# Constraint 3: Satisfy the daily demand
c3 = [(x[p][t], flow[p])for t in times for p in pumps]
bqm.add_linear_equality_constraint(
terms=c3,
constant=-demand,
lagrange_multiplier=28)
sampler = EmbeddingComposite(DWaveSampler())
samplest = sampler.sample(bqm, num_reads=1000)
sample = samplest.first.sample
total_flow = 0
total_cost = 0
print("ntAMtPM")
for p in pumps:
printout = "P" + str(p)
for time in range(2):
printout += "t" + str(sample[x[p][time]])
total_flow += sample[x[p][time]]*flow[p]
total_cost += sample[x[p][time]]*costs[p][time]
print(printout)
print("nTotal flow:t", total_flow)
print("Total cost:t", total_cost, 'n')
The Result:
Resource:
More examples: