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
Filter by
Sorted by
Tagged with
2 votes
2 answers
504 views

Qiskit compute mean expectation value

I want to calculate the mean expectation value of an PauliSumOp within qiskit after I executed a QAOA Circuit. My approach is the following: ...
3 votes
1 answer
124 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 ...
2 votes
0 answers
150 views

What are the important parameters when it comes to VQE algorithms in qiskit?

So I wrote an algorithm for a quadratic problem (qubo) and try to solve it. My question is why I don't get the correct results when running my algorithm on a quantum computer like IBM_manila. In the ...
• 21
3 votes
2 answers
478 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
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
2 votes
1 answer
145 views

Why do we add the cost function as a phase in QAOA?

For QAOA, my understanding is that after we derive our cost Hamiltonian: $H_c|x$>$=C(x)x$ where $C(x)$ is the cost function on input x. We exponentiate it: $e^{-iH_c\theta}$, so we can simulate ...
• 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} ...
4 votes
1 answer
406 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
1 vote
1 answer
239 views

Tweak the parameter p of QAOA in qiskit

I am solving a QUBO using QAOA. It works flawlessly with default parameters for smaller instances of the problem, but my RAM is saturated when I try to solve a problem of size 15. I suspect this can ...
• 231
3 votes
1 answer
392 views

QUBO defined in Qiskit/DOcplex: how to solve it using Pennylane?

I have a complex Integer Linear Programming model defined in DOcplex/Qiskit representing a combinatorial optimization problem. Using the Qiskit utils, it is possible to covert it to either an Ising ...
3 votes
1 answer
296 views

• 13
4 votes
2 answers
325 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
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
2 votes
1 answer
132 views

IBM Qiskit QAOA gate implementation question

In section $5.2$ of the QAOA chapter in Qiskit textbook, section $5.2$, state preparation uses the gate $U_{k,l}(\gamma) = e^{\frac{i \gamma}{2} (1-Z_k Z_l)}$. Later, in section $5.3$, this gate is ...
• 105
1 vote
0 answers
83 views

Will there be any difference in solution for a weighted and unweighted graph? I mean is there any relation between weight and solution?

I was working on max-cut problem. To do I have been given a graph of unweighted version, and I have to convert it into weighted version. I did it using qiskit. Now I was playing around the code, hence ...
2 votes
2 answers
2k views

Qiskit: Taking a QUBO matrix into `qubit_op'

I'm trying to solve the maximum independent set problem using Qiskit and the QAOA. I've a nice QUBO Matrix for this simple path graph: as so: My question is, how do I convert this into a general ...
• 209
5 votes
1 answer
891 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 ...
8 votes
2 answers
757 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 ...
6 votes
1 answer
541 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 ...