Quantum Programming Algorithms: Approximate Optimization
Feb 8, 2022
Quantum Programming, by Outline Algorithms: approximate optimization; 100 minutes; Feb 8, 2022
Copyright By PowCoder代写 加微信 powcoder
Hook: Our next quantum algorithm is the quantum approximate optimization algorithm, also known as QAOA. It solves a class of natural problems and is one of the best hopes for a quantum advantage in the 2020s.
Purpose: Persuade you that you can understand this algorithm.
1. We will make sure that everybody understands the class of problems. 2. We will show how QAOA searches a grid of options to find a good one. 3. We will look at Google’s experimental results for a graph problem.
Transition to Body: Now let us talk about the kind of problem that this algorithm solves.
Main Point 1: We will make sure that everybody understands the class of problems. [Each problem is an optimization problem, which QAOA solves approximately] [Such problems are NP-complete]
[QAOA has inspired researchers to design better classical algorithms]
Transition to MP2: Now let us look at how to solve the problem on a quantum computer.
Main Point 2: We will show how QAOA searches a grid of options to find a good one.
[The algorithm represents the problem as a function that marks good approximate solutions] [The algorithm varies two parameters and picks the best result]
[Two matrices separate and boost-the-amplitude of the good cases]
Transition to MP3: Now let us get into performance.
Main Point 3: We will look at Google’s experimental results for a graph problem. [They repeat the experiment 50,000 times and post-process to compensate for bias] [For hardware subgraphs, the results are independent of the number of qubits] [Noiseless simulation is much better than running on a noisy quantum computer]
Transition to Close: So there you have it.
Review: QAOA searches a grid of options to find a good approximation of the optimal solution
with high probability.
Strong finish: In 2019, DARPA is put $33 million into finding out whether QAOA on quantum computers is faster than classical algorithms on classical computers. If this effort succeeds, it will be a watershed moment for quantum computing.
Call to action: Think about other NP-complete problems that QAOA can solve.
Detailed presentation
Hook: Our next quantum algorithm is the quantum approximate optimization algorithm, also known as QAOA. It solves a class of natural problems and is one of the best hopes for a quantum advantage in the 2020s.
QAOA is an example of a variational algorithm. Variational algorithms are a particular class of hybrid algorithms, that is, algorithms that use both classical and quantum computation.
QAOA solves an NP-complete problem approximately. This is interesting because, at scale, NP-complete problems are intractable for classical computers. Many NP-complete problems are important in practice so classical computers solve them approximately. The question is: can QAOA give better approximate solutions than classical computers within the same time frame, or give as good solutions faster?
Purpose: Persuade you that you can understand this algorithm.
1. We will make sure that everybody understands the class of problems. 2. We will show how QAOA searches a grid of options to find a good one. 3. We will look at Google’s experimental results for a graph problem.
Transition to Body: Now let us talk about the kind of problem that this algorithm solves. Main Point 1: We will make sure that everybody understands the class of problems.
[Each problem is an optimization problem, which QAOA solves approximately]
The MaxSAT problem is: given a Boolean formula that is a conjunction of some clauses, satisfy as many of the clauses as possible. We will focus on restricted form of MaxSAT that has all the essential computational challenges of the general problem. This restricted form is called Max2SAT and has the following definition.
The Max2SAT problem:
Intuition: n variables, m clauses, satisfy as many clauses as possible.
Input: an integer t ∈ 1..m and a Boolean formula ∧mj=1 (lj1 ∨ lj2).
Terminology: we call each (lj1 ∨ lj2) a clause, and we call each ljq a literal.
Notation: each literal ljq is either a variable xp or the negation of a variable, written ¬xp. Convention: the variables form the set x0, . . . , xn−1.
Notation: we use z to range over mappings from variables to Booleans.
Output: 1 if ∃z: z satisfies at least t of the clauses, and 0 otherwise.
Here is an example instance of the Max2SAT problem.
t = 8 (x1 ∨x2)∧(x2 ∨¬x5)∧(¬x3 ∨¬x4)∧ (x2 ∨¬x6)∧(¬x3 ∨¬x5)∧(x3 ∨¬x4)∧ (¬x4 ∨x5)∧(x3 ∨¬x0)∧(x4 ∨x0)
Here we have a formula with 9 clauses and the goal to satisfy at least 8 of them. Notice that the formula uses 7 variables, called x0, . . . , x6.
[Such problems are NP-complete]
Intuitively, Max2SAT is NP-complete because we have no easy way to satisfy more and more clauses in an efficient way. Specifically, if we try a strategy that tries to satisfy more and more clauses, we can get stuck in a local optimum and miss the best solution.
In an attempt to solve the problem instance above, we might begin with a random assignment, such as the one that assigns true to every variable. Now we can evaluate how many clauses this assignment satisfies, and we will find that it satisfies 7 clauses. How do improve this assignment to a different one that satisfies 8 clauses? Perhaps we can think of something by studying this particular formula, like we could change the assignment of x4 from true to false. Indeed, this change would give us an assignment that satisfies 8 clauses. However, in general, we have no efficient strategy for doing such an improvement in a way that gets us to a global maximum or beats a given t.
[QAOA has inspired researchers to design better classical algorithms]
QAOA solves MaxSAT approximately and, at the time came out in 2014, it was the best algorithm on any kind of computer. Then in 2015 the classical-algorithms people upped their game and presented a classical algorithm that beats QAOA in certain ways. However, in 2016 the QAOA people published a paper that argues that QAOA may give a quantum advantage over classical approximation algorithms. In 2019, a group of researchers published an improvement of QAOA.
Transition to MP2: Now let us look at how to solve the problem on a quantum computer. Main Point 2: We will show how QAOA searches a grid of options to find a good one.
[The algorithm represents the problem as a function that marks good approximate solutions] Let us represent a mapping z as a bit string in {0, 1}n with the idea that z maps xk to the k’th bit in the bit string. Henceforth, when we write z, we mean the bit string representation.
Given z ∈ {0, 1}n and a Boolean formula ∧mj=1 (lj1 ∨ lj2), define
Countj(z) =
Count(z) Cj|z⟩
Σmj=1 Countj(z) Countj(z) |z⟩
1 if z satisfies the j’th clause 0 otherwise
Count(z) |z⟩ = Σmj=1 Countj(z) |z⟩ = Σmj=1 Cj|z⟩ Σn−1 NOTk
NOT ⊗I⊗(n−1) + I ⊗NOT ⊗I⊗(n−2) + … + I⊗(n−1) ⊗NOT
Notice that Count is a
is a function in the quantum world: it maps quantum states to quantum states (well, unnormalized quantum states). The idea is that C uses Count to mark the good cases. Specifically, in C|z⟩, the amplitude of |z⟩ is the number of clauses that z satisfies.
In the definition of B, we use NOTk as informal notation to mean application of NOT to the k’th qubit.
From C we will build a separator and from B we will build a mixer. 4
function in the classical world: it maps bit strings to numbers. In contrast, C
[The algorithm varies two parameters and picks the best result]
The algorithm uses two parameters (γ, β) ∈ [0, 2π] × [0, π] to get variation in the results of the runs. From C, B, γ, β, we build two rotation matrices: Sep(γ) = e−iγC and Mix(β) = e−iβB. We will call Sep(γ) the separator matrix, while we will call Mix(β) mixer matrix.
Here is QAOA:
for many different choices of (γ, β) ∈ [0, 2π] × [0, π] { measure Mix(β) Sep(γ) H⊗n |0n⟩
pick the measurement z that maximizes Count(z).
Here is the intuition behind how the algorithm works.
First we use H⊗n to create a uniform superposition of all bit strings. The idea of a uniform superposition is that every bit string has the same chance of being measured.
Then we use Sep(γ) to mark the good cases with special amplitudes, while maintaining the uniform superposition.
Finally, we use Mix(β) to boost the amplitudes of the good cases.
[Two matrices separate and boost-the-amplitude of the good cases]
The separator matrix is Sep (γ ) = e−iγ C . Notice that C is a diagonal matrix, hence Hermitian, hence e−iγC is a unitary matrix. Indeed, e−iγC is a rotation matrix. Let us calculate to see some details of Sep(γ).
Sep(γ) = e−iγC
= e−iγ Σmj =1 Cj
= Πmj=1 e−iγCj
The third step is called Trotter decomposition and is correct because the Cj matrices commute. Let us do a case analysis of e−iγCj. The analysis begins with considering Cj. Recall:
Countj(z) =
1 if z satisfies the j’th clause 0 otherwise
Cj|z⟩ = Countj(z) |z⟩
We have two cases, 0 and 1, of Countj, so we have two cases of Cj:
{ |z⟩ if Countj(z) = 1 Cj|z⟩ = 0 if Countj(z) = 0
{ e−iγ |z⟩ |z⟩
if Count (z) = 1 j
e−iγCj|z⟩ =
Above we use I to denote the identity matrix and we use 0 to denote the vector that is all 0.
Now we can continue the calculation of Sep(γ):
Sep(γ) Σz∈{0,1}n az|z⟩ = Πmj=1 e−iγCj Σz∈{0,1}n az|z⟩ = Σz∈{0,1}n az Πmj=1 e−iγCj |z⟩
= Σz∈{0,1}n az (e−iγ)Count(z) |z⟩ 5
if Countj(z) = 0
So, |z⟩ gets a factor e−iγ for each clause that z satisfies.
The next task is to design a circuit for Sep(γ). We will do that by adding a helper qubit.
We will give an example of the construction of the circuit. Consider the following formula with
two variables and two clauses:
x0 ∧(x0∧x1)
We would have some work to do to get this formula into the format that we used at the beginning
of the lecture, but let us ignore that. We have:
Sep(γ) (a00|00⟩ + a01|01⟩ + a10|10⟩ + a11|11⟩)
= a00|00⟩ + a01|01⟩ + (e−iγ)1a10|10⟩ + (e−iγ)2a11|11⟩ Notice that we changed the amplitude of the good cases.
We can get this
Now we can do the
effect via the following circuit:
(a00|00⟩ ⊗ |1⟩ + a01|01⟩ ⊗ |1⟩ + a10|10⟩ ⊗ |1⟩ + a11|11⟩) ⊗ |1⟩
a00|00⟩ ⊗ |1⟩ + a01|01⟩ ⊗ |1⟩ + a10|10⟩ ⊗ (e−iγ)1|1⟩ + a11|11⟩ ⊗ (e−iγ)2|1⟩ a00|001⟩ + a01|011⟩ + (e−iγ)1a10|101⟩ + (e−iγ)2a11|111⟩
For example, let us
consider γ = π4 . We have
e−iγ = ei(−γ) = cos(−γ) + i sin(−γ) = cos(γ) − i sin(γ)
= √1 − i√1 22
(√1 −i√1 )2 = 12(1−i)2 = 12(−2i) = −i 22
Now we turn our attention to the mixer matrix.
The mixer matrix is Mix(β) = e−iβB. Recall:
B = Σn−1 NOTk
We can look up a formula for exponentiation of matrices and find that
Mix(β) = e−iβB = e−iβ Σn−1 NOTk = Πn−1 e−iβNOTk = (⊗n) R (2β) k=0 k=0 x
calculation again with this circuit as Sep(γ) and with a helper qubit.
For example, for β = π2 :
Another example, for β = π4 :
( cos(β) −isin(β) ) −i sin(β) cos(β)
Rx(22)= −i0 =−iNOT
R(2π) = 2 2 = √1 (I−iNOT) x4−i√1√1 2
Another example, for β = π8 :
(1√√ 1√√) (√√ √√)
π 2+ 2 −i 2− 2 1 Rx(2)=2√√√2√= √√√√
2+ 2 −i 2− 2 8 −i12 2− 2 12 2+ 2 2 −i 2− 2 2+ 2
Now let us do a run of QAOA on the Boolean formula from earlier: x0 ∧(x0∧x1)
We will do a single iteration of the for-loop with a single choice of (γ,β). We will pick γ = π4 and
π4 . We will ignore the helper qubit that we need along the way. Mix(β) Sep(γ) H⊗2 |00⟩
Mix(β) Sep(γ) 12(|00⟩ + |01⟩ + |10⟩ + |11⟩) Mix(β) 12(|00⟩ + |01⟩ + (√1 − i√1 )|10⟩ − i|11⟩)
(√1 (I −i NOT)⊗ √1 (I −i NOT))12(|00⟩+|01⟩+(√1 −i√1 )|10⟩−i|11⟩) 2222
14((I −i NOT)⊗(I −i NOT))(|00⟩+|01⟩+(√1 −i√1 )|10⟩−i|11⟩) 22
14((|00⟩ + |01⟩ + (√1 − i√1 )|10⟩ − i|11⟩) + (−i|10⟩ − i|11⟩ + (−i√1 − √1 22 22
)|00⟩ − |01⟩) +
(−i|01⟩ − i|00⟩ + (−i√1 − √1 )|11⟩ − |10⟩) + (−|11⟩ − |10⟩ − (√1 − i√1 22 22
14((1+(−i√1 − √1 ))|00⟩ + (−i−(√1 −i√1 ))|01⟩ + 22 22
((√1 −i√1 )−i−2)|10⟩ + (−2i+(−i√1 − √1 )−1)|11⟩) 22 22
41(((1− √1 )− √1 i)|00⟩ + (−√1 −(1− √1 )i)|01⟩ + 2222
((−2+ √1 )−(1+ √1 )i)|10⟩ + (−(1+ √1 )−(2+ √1 )i)|11⟩) 22 22
)|01⟩ + i|00⟩))
Now we can calculate the probabilities of measuring each of the four cases:
00:2− 2≈3.7% 01:2− 2≈3.7%
Here we can see that the two bit strings (00, 01) that satisfy 0 clauses each has low probability, while the bit string (10) that satisfies 1 clause has much higher probability, and the bit string (11) that satisfies 2 clauses has the highest probability. So, chances are that we will run QAOA on the formula, measure 11, check that 11 satisfies both clauses, and be done.
QAOA has a more general version that in each iteration does p applications of (Mix(β) Sep(γ)). Each application uses a different pair (γ, β). In the limit (p → ∞), this gives the best solution.
Transition to MP3: Now let us get into performance.
paragraphMain Point 3: We will look at Google’s experimental results for a graph problem.
[They repeat the experiment 50,000 times and post-process to compensate for bias]
Google people have published papers on trying to achieve a quantum advantage. One of those papers is from April 2020 and is called “Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor”, and is written by Google AI Quantum and Collaborators (many authors). The paper describes a large-scale experiment with QAOA and can be found on ArXiv, https://arxiv.org/abs/2004.04197.
The paper is all about undirected graphs and the problems that we can consider for such graphs. Each edge has a weight in {−1, 0, −1}. Many problems can be modeled once we assign each edge a weight in {−1, 0, −1}. For a graph, we can define a cost function that works with the nodes, the edges, and the edge weights. Given such a cost function, we can define a problem that is about minimizing or maximizing the cost function.
The paper describes how to run QAOA to solve the MaxCut problem. The MaxCut problem is to find a cut whose size is at least the size of any other cut. A cut divides the nodes into two subsets and then we consider the edges that cross from one subset to the other. In the special case where every edge weights is 1, the goal is to maximize the number of edges that cross from one subset of nodes to the other. MaxCut for 3-regular graphs is NP-complete. In a 3-regular graph, every node has 3 neighbors.
Google ran the experiment on the Sycamore quantum computer. The Sycamore quantum computer has low error rates compared to other quantum computers with superconducting qubits. Specifically, the 2-qubit SYC gate has 99.4 percent fidelity, while the measurement fidelity is 95.9 percent per qubit.
The Sycamore quantum computer has 54 qubits, though the paper uses a maximum of 23 qubits. Here is the layout of those 23 qubits.
10:6− 2≈28.6% 11:6+3 2≈64.0%
Notice that the layout is a planar graph, that is, no edges cross each other.
Now we can consider two kinds of graphs: (1) subgraphs of the hardware graph and (2) other
graphs. We should expect better performance of QAOA for subgraphs of the hardware graph. Measurement has a fairly low fidelity of 95.9 percent per qubit. Additionally, the measurement
has a bias which we can model by talking about
p0 as the error that the measurement got changed from 0 to 1, and
p1 as the error that the measurement got changed from 1 to 0.
The paper uses post-processing to compensate for bias in the measurements. This post-processing
is computationally intensive and is done as part of the classical-quantum hybrid approach.
Above, the first diagram shows p0, p1 before post-processing, while the second diagram shows p0, p1 after post-processing. We see how especially p1 is much more even across the qubits.
The following figure reports on runs of QAOA with p = 1. Those runs use Model Gradient Descent to find values of γ,β. They estimate each expectation value by repeating the experiment 50,000 times. The real-time speed of the computation is that they measure 5,000 bitstrings per second.
Above we see a good correspondence between the experimental and the theoretical landscapes for problems of large size and complexity. Each iteration consists of 6 energy evaluations to estimate the gradient, and each energy evaluation used 25,000 circuit repetitions.
The Sherrington-Kirkpatrick model (also known as the SK Model) uses a fully connected graph in which each edge weight is 1 or −1.
[For hardware subgraphs, the results are independent of the number of qubits] The diagram below shows QAOA performance as a function of the number of qubits.
We see that noiseless is much better than noisy, both for hardware subgraphs and for the SK Model. Notice that for hardware subgraphs, the results are independent of the number of qubits. The paper says that theory predicted this result: errors stay local. Notice also that for fully connected graphs, the results get worse with the number of qubits. Reason: errors propagate quickly.
[Noiseless simulation is much better than running on a noisy quantum computer]
Figure 5 shows that increasing p (in QAOA) is good for noiseless but fairly neutral for noisy.
The experiments show that the results from a quantum computer are much worse than from
simulation. The quest for a quantum advantage on practical problems continues. Transition to Close: So there you have it.
Review: QAOA searches a grid of options to find a good approximation of the optimal solution with high probability.
Strong finish: In 2019, DARPA is put $33 million into finding out whether QAOA on quantum computers is faster than classical algorithms on classical computers. If this effort succeeds, it will be a watershed moment for quantum computing.
Call to action: Think about other NP-complete problems that QAOA can solve. 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com