Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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).

Filter by
Sorted by
Tagged with
17 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 ...
Malcolm Regan's user avatar
16 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 ...
hopefully coherent's user avatar
14 votes
1 answer
1k 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 ...
Nikita Nemkov's user avatar
12 votes
1 answer
428 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 ...
Chao-Hua Yu's user avatar
10 votes
1 answer
670 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, ...
asdf's user avatar
  • 503
9 votes
2 answers
860 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 ...
Nepomuk Hirsch's user avatar
9 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 ...
karolyzz's user avatar
  • 279
8 votes
1 answer
4k 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. ...
John Parker's user avatar
  • 1,111
8 votes
1 answer
450 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 ...
dncolomer's user avatar
  • 148
7 votes
2 answers
192 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 ...
Martin Vesely's user avatar
6 votes
1 answer
2k 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 ...
26118in's user avatar
  • 508
6 votes
1 answer
716 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 ...
Nepomuk Hirsch's user avatar
6 votes
1 answer
432 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-...
John Wong's user avatar
  • 291
6 votes
1 answer
103 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 ...
Alexey Uvarov's user avatar
6 votes
0 answers
108 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 ...
Hannah's user avatar
  • 529
5 votes
1 answer
533 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}...
Martin Vesely's user avatar
5 votes
1 answer
982 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 ...
John Parker's user avatar
  • 1,111
5 votes
1 answer
1k 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 ...
kontojulii's user avatar
5 votes
1 answer
110 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 ...
Soumik Adhikary's user avatar
5 votes
0 answers
127 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 ...
underdog987's user avatar
4 votes
1 answer
2k 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. ...
EventicTortoise's user avatar
4 votes
1 answer
318 views

Are there techniques to reduce the number of Pauli strings in a Hamiltonian?

Suppose $H=\sum_{i \in n} c_i h_i$ is a generic Hamiltonian. Is there a way to find $\tilde{H} = \sum_{j \in m} d_j h_j$ where $m < n$ is a user defined cut-off parameter that would accurately ...
squareroottwo's user avatar
4 votes
1 answer
177 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 ...
IsalanOnkar's user avatar
4 votes
1 answer
165 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 ...
Dina Abdelhadi's user avatar
4 votes
1 answer
525 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: ...
Hannah's user avatar
  • 529
4 votes
1 answer
248 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{...
nuemlouno's user avatar
  • 177
4 votes
1 answer
535 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 ...
Sup's user avatar
  • 231
4 votes
1 answer
468 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 ...
Himera Ephemera's user avatar
4 votes
2 answers
399 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 ...
jolene's user avatar
  • 219
4 votes
1 answer
134 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 ...
Bidon's user avatar
  • 818
4 votes
1 answer
138 views

Retrieving job result attributes in Qiskit

I am trying to optimize a Hamiltonian using QAOA in IBM Qiskit. I used the following 'minimize' function to get my result. (I am not including the whole code because it will get unnecessarily long). <...
Amrita P's user avatar
4 votes
1 answer
214 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 ...
ile2N's user avatar
  • 155
4 votes
1 answer
242 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 ...
cnada's user avatar
  • 4,754
4 votes
0 answers
163 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 ...
user26100's user avatar
4 votes
0 answers
132 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 ...
Juri V's user avatar
  • 105
4 votes
1 answer
315 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 ...
3.14159's user avatar
  • 41
4 votes
0 answers
174 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 ...
bubakazouba's user avatar
4 votes
0 answers
118 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} ...
user39726's user avatar
4 votes
0 answers
120 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 ...
peachnuts's user avatar
  • 1,393
4 votes
0 answers
147 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\,\,...
Sup's user avatar
  • 231
4 votes
0 answers
58 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 ...
Nikita Nemkov's user avatar
4 votes
0 answers
228 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 ...
Masamune's user avatar
4 votes
0 answers
941 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 ...
ile2N's user avatar
  • 155
3 votes
2 answers
442 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 ...
Jeff24's user avatar
  • 141
3 votes
1 answer
440 views

Do VQE and QAOA use the same Hamiltonian?

In this paper, it talks about the 2-local Hamiltonian in the form: $H = \sum_{(u,v)\in E} H_{uv} + \sum_{k \in v} H_k $ It also says the Ising model, Heisenberg model, XY model and QAOA are in the ...
peachnuts's user avatar
  • 1,393
3 votes
1 answer
100 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?
Hannah's user avatar
  • 529
3 votes
1 answer
366 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, \...
user1936752's user avatar
  • 2,997
3 votes
1 answer
656 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 ...
Marion's user avatar
  • 635
3 votes
2 answers
423 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 ...
underdog987's user avatar
3 votes
2 answers
595 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 ...
bubakazouba's user avatar