Questions tagged [qaoa]
For questions about the Quantum Approximate Optimization Algorithm (QAOA), first introduced in Farhi, Goldstone, Gutmann 2014 (https://arxiv.org/abs/1411.4028).
147
questions
15
votes
1
answer
3k
views
Is VQE a class of algorithms or a specific algorithm?
Is VQE a class of algorithms or a specific algorithm? For example, is QAOA a VQE or is VQE an algorithm distinct from QAOA that solves the same class of problems?
If VQE is a specific algorithm, what ...
- 703
14
votes
1
answer
3k
views
What is the difference between QAOA and Quantum Annealing?
Edward Farhi's paper on the Quantum Approximate Optimization Algorithm
introduces a way for gate model quantum computers to solve combinatorial optimization algorithms. However, D-Wave style quantum ...
12
votes
1
answer
374
views
What does the paper "Training Variational Quantum Algorithms Is NP-Hard (Phys. Rev. Lett. 127, 120502)" mean?
I have seen the recent paper "Training Variational Quantum Algorithms Is NP-Hard (Phys. Rev. Lett. 127, 120502)" and the authors stated that training the classical optimization in ...
- 193
12
votes
1
answer
834
views
Why exactly are variational algorithms considered promising?
There is obviously a great deal of work happening at the moment on variational quantum algorithms. However, I'm struggling to understand why exactly are they considered promising? Looking through some ...
- 1,455
10
votes
1
answer
638
views
Barren plateaus in quantum neural network training landscapes
Here the authors argue that the efforts of creating a scalable quantum neural network using a set of parameterized gates are deemed to fail for a large number of qubits. This is due to the fact that, ...
- 493
8
votes
1
answer
3k
views
What's the role of mixer in QAOA?
In QAOA algorithm, two terms are being discussed; 1) clause or cost (C) Hamiltonian and 2) mixer consisting of pauli X gates.
What is the role of this mixer? Not clear why it comes after the C. ...
- 1,011
8
votes
2
answers
684
views
Why does QAOA achieve quantum supremacy in an algorithmic sense?
In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15):
"If [...] the QAOA outperforms all known classical algorithms ...
- 445
8
votes
1
answer
429
views
Is there a mistake in the VQE Ansatz in Cirq's tutorial?
I have been going through Cirq's VQE background tutorial and after examining the Ansatz it seems to me that the only layer that actually affects the final measurement is the rot_x_layer. The other ...
- 138
8
votes
1
answer
1k
views
QUBO, Ising Hamiltonians and VQA
I understand that usually the combinatorial optimisation problems are turned into QUBO, which has a very simple mapping to Ising Hamiltonians. Ising Hamiltonians in turn have the desired properties of ...
- 269
7
votes
2
answers
137
views
Quantum annealing - studies showing empirical evidence for better performance in comparison with classical computers
Currently, it is not known wheter quantum anneling or algorithms like VQE and QAOA for general purpose quantum computers bring about any increase in computational power. However, there are some ...
- 13.5k
6
votes
1
answer
467
views
Properties of QAOA
The QAOA algorithm consists of two elements:
The outer loop, basically a classical optimization algorithm
The quantum circuit, taking $2p$ parameters (where $p$ is the number of layers, where each ...
- 445
6
votes
1
answer
311
views
Why QAOA with $p \rightarrow \infty $ gives the optimal solution?
In the QAOA paper, it is shown that the optimal value of the p-ansatz $M_p$ converges to $\max_z C(z)$ as $p \rightarrow \infty$ on page 10. The proof is to relate to QAOA by considering the time-...
- 291
6
votes
0
answers
99
views
In QAOA why do we need $m \log(m)$ repetitions to get at least $F_{p}(\beta , \gamma) - 1$ with probability of $1 - 1/m$?
In the original QAOA paper from Farhi
https://arxiv.org/pdf/1411.4028.pdf,
it is stated in chapter 2 last paragraph (page 6) that: when measuring $F_{p}(\beta , \gamma)$ we get an outcome of at least ...
- 519
5
votes
1
answer
1k
views
How to show mathematically the equivalency between Ising Model and QUBO?
It is said that the Ising Model using spin variables $s ∈ \{−1, 1\}$
$$H(s)=\sum_{i}h_is_i+\sum_{i<j}J_{ij}s_is_j,$$
and a Quadratic Unconstrained Binary Optimization (QUBO) problem with binary ...
- 458
5
votes
1
answer
470
views
Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?
Quantum annealers are single purpose machines allowing to solve quadratic unconstrained binary optimization (QUBO) problems. QUBO problems have following objective function:
$$
F=-\sum_{i<j}J_{ij}...
- 13.5k
5
votes
1
answer
821
views
Solving higher-order (unconstrained) binary optimization problems with QAOA without quadratization
I am aware that it's possible to use QAOA to solve QUBO problems. However, I've recently seen some sources mentioning the possibility of solving HOBO/HUBO problems using QAOA as well [1][3].
While I ...
- 51
5
votes
1
answer
76
views
Recent experimental demonstrations of variational quantum algorithms?
I am interested in the recent experimental demonstrations of variational quantum algorithms.
Can someone please provide me with a list of references of recent experimental demonstrations of ...
5
votes
0
answers
74
views
How to use Warm-Start QAOA in QisKit to solve non-convex QUBO problem?
I have a non-convex QUBO problem that I'd like to solve by warm-starting QAOA with a solution obtained from a continuous relaxation solution obtained by a classical algorithm. The specifics of the ...
- 111
4
votes
1
answer
1k
views
Calculating the ground states of an Ising Hamiltonian on a real quantum computer
I have followed this tutorial and based on it, I've written the following function in qiskit, which can explicitly calculate the ground states of a transverse-field Ising Hamiltonian.
...
4
votes
1
answer
143
views
In QAOA, why do we pick the initial Hamiltonian $B$ to be $\sigma_x$ applied to each qubit?
In QAOA 1, why do we pick the initial Hamiltonian $B$ to be $\sigma_x$ applied to each qubit? Would it be possible to pick $B$ to be an application of $\sigma_z$'s instead? Then $C$ and $B$ would be ...
- 456
4
votes
1
answer
432
views
How does the classical optimization of the angles $\gamma$ and $\beta$ in QAOA work?
I have been trying to implement QAOA with classical optimization of the angles $\gamma$ and $\beta$, but I I'm failing at the classical part.
In paper Quantum Approximate Optimization Algorithm: ...
- 519
4
votes
1
answer
164
views
Derivation of QAOA from AQC
In adiabatic quantum optimization we start with an initial Hamiltonian $H_0$ and then adiabatically evolve from $H_0$ to $H_P$ (problem hamiltonian) for a time $T$ according to
\begin{equation}\label{...
- 177
4
votes
1
answer
341
views
How to theoretically compare the complexity of quantum and classical algorithms?
I am working on reducing an NP class problem to a QUBO so can be solved with QAOA. I know that there is not a practical way to compare the performance as there is no QPU with enough qubits. I am doing ...
- 101
4
votes
1
answer
339
views
Is the cost Hamiltonian unitary in QAOA?
I am trying to implement QAOA and there are things I don't understand at all.
The expansion of $H$ into Pauli $Z$ operators can be obtained from the canonical expansion of the cost-function $C$ by ...
4
votes
2
answers
309
views
Statevector Simulation of QAOA always finds exact solution
My question is simple: does applying QAOA with a statevector simulation always result in a perfect solution?
I'm trying to calculate the best $\gamma$ & $\beta$ that solve certain problems but my ...
- 209
4
votes
1
answer
122
views
Resource recommendation on quantum simulations
I would like to know more about quantum simulations, so as to start on a few standard physical models (maybe particle in a box, harmonic oscillator, etc.) and then build up on more complex things. But ...
- 808
4
votes
1
answer
168
views
Classical optimisation of angles in QAOA for TSP gets stuck in local minima?
I have been trying to implement a QAOA for solving a traveling salesman problem (TSP) using qulacs and python. However, even for ...
- 145
4
votes
1
answer
169
views
QAOA and symmetry effects on the angles
In this paper, QAOA on Maxcut shows symmetries that allow them to restrict their search space intervals. But how do they find such intervals knowing that in the original QAOA angles $\gamma,\beta$ are ...
- 4,644
4
votes
0
answers
117
views
Probability inequality for Quantum Approximate Optimization Algorithm (QAOA)
In arXiv:2207.14734 the authors claim that it is "straightforward to show that" their equation 8 holds:
$$\mathrm{Pr}_{x\sim q}[x:f(x)\geq \mu] \geq \frac{1}{M}$$
where we have an objective ...
- 105
4
votes
0
answers
135
views
Why does QAOA's performance monotonically increase as p increases?
From A Quantum Approximate Optimization Algorithm - Farhi et al.
The Quantum Approximate Optimization Algorithm has the key feature that as
p
increases the approximation improves. We contrast this to ...
- 261
3
votes
2
answers
367
views
What exactly happening in QAOA in a general way?
So I know that in QAOA we have the two hamiltonians. Mixer and Cost Hamiltonian.
Lets start:
First we have our Qubits which get in the Superposition if we add the Hadamard Gate.
Then we have the both ...
- 141
3
votes
1
answer
83
views
Papers on classical optimization in QAOA
Are there any papers on the classical optimization part of QAOA?
What is the most efficient method now?
And how is the classical optimization classified?
- 519
3
votes
1
answer
328
views
QAOA for MaxCut - Algorithm motivation
In the QAOA algorithm for MaxCut, the authors construct a very specific scheme where the qubits (corresponding to the vertices of the graph) are transformed using a sequence of unitaries
$$|\gamma, \...
- 2,439
3
votes
1
answer
118
views
Does QAO Ansatz have any better performance guarantees than QAOA?
QAOA is a well-known heuristic for solving optimization problems, and it has the desirable property that as p -> infinity, the true minimum objective function value is reached.
There is a ...
- 61
3
votes
1
answer
428
views
Choosing a different optimizer when running QAOA in qiskit
I am trying to reproduce the QAOA example from https://qiskit.org/textbook/ch-applications/qaoa.html and learn how to opt for a different optimizer.
The relevant block in the example is (towards the ...
- 585
3
votes
2
answers
420
views
Why do we decompose the hamiltonian into Pauli strings to measure the expectation value?
Measuring the expectation value of a hamiltonian is an essential step in some algorithms like QAOA.
I noticed that the procedure always starts with decomposing the hamiltonian into a sum of Pauli ...
- 261
3
votes
1
answer
66
views
Is $\gamma \in [0,2 \pi]$ or $\gamma \in [0,\pi]$ in $CU1(2\gamma)_{(i,j)} $?
When wanting to find the groundstate of this Hamiltonian with QAOA:
\begin{equation}
H_{C} =\sum_{i }^{n}(1 - Z_{i})/2 + \sum_{\{i,j\}\in \overline{E} } - 2(1 - Z_{i})(1 - Z_{j})/4
\end{equation}
...
- 519
3
votes
2
answers
163
views
Does QAOA require that the problem Hamiltonian be an Ising Hamiltonian as a quadratic function of the spin variables?
In the context of QAOA, I often see the problem Hamiltonian being called an "Ising Hamiltonian", and shortly after, I that the Hamiltonian is a quadratic function of the spin variables.
Is ...
- 111
3
votes
2
answers
271
views
qiskit qaoa.compute_minimum_eigenvalue
I am having some trouble running the compute_minimum_eigenvalue method from qiskit's QAOA: the documentation states that one ...
- 113
3
votes
1
answer
850
views
How does the performance of QAOA and VQE compare to Grover's?
I believe finding the optimal solution is guaranteed for Grover's Algorithm along with quadratic speed-up according to Nielsen and Chuang's book.
I wonder if there is any statement regarding QAOA and ...
- 1,011
3
votes
1
answer
438
views
Can QAOA solve a constraint optimization problem?
Can QAOA solve a constraint binary optimization problem? QAOA is short for Quantum Approximate Optimization Algorithm. I read the information https://qiskit.org/textbook/ch-applications/qaoa.html.
But ...
- 61
3
votes
1
answer
152
views
To find the best angles in QAOA why we do not optimize over a maximum ofall shots instead of a mean?
When finding the best angles for QAOA we optimize over $F_{p}(\beta , \gamma) = \langle \psi_p(\gamma,\beta)|C|\psi_p(\gamma,\beta)\rangle $.
In each optimization step we simulate the circuit $m$ ...
- 519
3
votes
1
answer
183
views
QAOA Belongs into VQE or the other way around?
I have been reading a couple of papers in the arxiv and wanted to get a clarification regarding the relation between these two methods; is one a subset of the other?
- 983
3
votes
1
answer
270
views
QAOA calculation expectation value
Given the QAOA circuit $U(\vec\gamma, \vec\beta)$, associated to some cost hamiltonian $H_C$, and evolving the state $|0\rangle^{\otimes n}$ into $|\vec\gamma, \vec\beta\rangle = U(\vec\gamma, \vec\...
- 631
3
votes
1
answer
183
views
How to use Clifford Data Regression for the MaxCut Problem
i read about Clifford Data Regression in https://arxiv.org/pdf/2005.10189.pdf.
If I have understood this correctly, then one receives the mitigated expected value of an observable from CDR.
For the ...
- 53
3
votes
1
answer
238
views
What is the relationship between the mixing operators and initial states found in QAOA and Quantum Annealing?
In many papers, the QAOA is shown to be intimately related to Quantum Annealing/Quantum Adiabatic Algorithm/Adiabatic Quantum Optimization.
The mixing operator in the QAOA is described by Hadfield as ...
- 41
3
votes
1
answer
133
views
What is the implication of locality in QAOA?
Suppose I am solving the TSP formulated as a QUBO problem using QAOA. I understand from the original paper that there is a parameter $p$ which sets the number of steps used in the alternating ansatz. ...
- 626
3
votes
1
answer
106
views
How does the fact that the output of a quantum circuit cannot be efficiently simulated classically help for optimisation?
This question refers principally to the article where for a low-depth circuit QAOA, the output cannot be efficiently simulated classically. I am wondering how this kind of quantum supremacy matters ...
- 4,644
3
votes
1
answer
53
views
How to sanity check QAOA cost Hamiltonian?
I'm trying to learn QAOA and how to apply it to a complex combinatorial problem. But for the purpose of this question I'll use the common example
MaxCut.
I'd like to know if I've set up my cost ...
- 33
3
votes
1
answer
104
views
Understanding QAOA from Basics/scratch
Recently after working on QAOA with finance and graph coloring problems. I have started exploring the QAOA from scratch. I would like to understand the QAOA derivation mathematically and have started ...
- 31