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).
153
questions
16
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 ...
- 713
15
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 ...
13
votes
1
answer
899
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,515
12
votes
1
answer
402
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 ...
- 303
10
votes
1
answer
656
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,031
8
votes
2
answers
751
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 ...
- 485
8
votes
1
answer
441
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
2k
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
161
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.6k
6
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 ...
- 478
6
votes
1
answer
538
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 ...
- 485
6
votes
1
answer
350
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
104
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
495
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.6k
5
votes
1
answer
890
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
92
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
99
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
156
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
459
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
200
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
405
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 ...
- 231
4
votes
1
answer
885
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,031
4
votes
1
answer
373
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
323
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
126
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 ...
- 818
4
votes
1
answer
185
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 ...
- 155
4
votes
1
answer
199
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
93
views
Qiskit QAOA optimization does not work when setting simulation seed in AerSampler
I am using Qiskit's QAOA for optimization and I would like to extract the probabilities distribution obtained in the optimization loop when running the circuit with the optimal parameters set. To do ...
- 41
4
votes
0
answers
126
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
71
views
Does the Lie closure of a set of Hamiltonians describe all unitaries you can generate with them?
Suppose we have $k$ Hermitian matrices $H_1, ..., H_k \in M_d(\mathbb{C})$. Define $\mathfrak{g} = \langle iH_1, ... iH_k \rangle_{\text{Lie}}$ to be the Lie algebra generated by these Hermitian ...
- 684
4
votes
1
answer
272
views
Qiskit unable to transpile the circuit for Rigetti Aspen M 1 on AWS
I am trying to run a Qiskit QAOA algorithm on AWS Rigetti Aspen M 1 Backend using qiskit braket provider. However qiskit is not able to properly transpile the circuit
...
- 41
4
votes
0
answers
148
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 ...
- 271
4
votes
0
answers
112
views
How to optimise QAOA
I have a similarly naive question about the classical part of the optimisation in the Quantum Approximate Optimization Algorithm. Specifically, the cost function is given prescribed as
\begin{align}
...
- 83
4
votes
0
answers
87
views
Does noise model in qiskit impact the optimized parameters for QAOA?
I have read this paper about the effects of quantum noise on QAOA.
In the conclusion, it says: QAOA is a noise-tolerant algorithm, quantum noise does not change the QAOA quantum circuit parameter ...
- 1,343
4
votes
0
answers
137
views
QAOA for Binary Optimization
I have reduced an optimization problem to a Binary Integer Linear Programming model as follows:
$$\sum_{j=1}^{2^n-1} f(C_j)x_j \rightarrow \max$$
$$\text{subject to} \sum_{j=1}^{2^n-1} S_{i,j}x_j=1\,\,...
- 231
4
votes
0
answers
56
views
If a hybrid classical+quantum algorithm can achieve quantum advantage, does this mean that the quantum part alone can?
Take for example a variational algorithm which has a classical optimization part and a quantum sampling part. In principle, the quantum part can be simulated by another classical computer given ...
- 1,515
4
votes
0
answers
211
views
Implemented QAOA returns wrong result
I try to apply QAOA algorithm to find minimal energy state of the Hamiltonian:
$H_A = \frac{1}{2}\sigma_z^1 + \frac{1}{2}\sigma_z^1\sigma_z^2$
It is expected that with p=2 my variational should ...
- 63
4
votes
0
answers
884
views
qiskit: Traveling Salesman Problem using QAOA fails for more than 3 cities
I tried to implement the traveling salesman problem (TSP) using QAOA with qiskit. I worked with this qiskit QAOA tutorial and this qiskit minimum eigen optimizer tutorial, where they implement a TSP ...
- 155
3
votes
2
answers
396
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
98
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
351
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,597
3
votes
1
answer
143
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
481
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 ...
- 615
3
votes
2
answers
247
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
475
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 ...
- 271
3
votes
1
answer
70
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
313
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
283
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