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

50 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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
94 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 ...
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
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 ...
273 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
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
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} ...
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
137 views

1 vote
132 views

### QAOA with Qiskit: Is the initial state affected by the noise model?

I'm doing a simulation of the QAOA algorithm with noise via the QAOA class of Qiskit 0.19. Here's (part of) my code: ...
• 33
1 vote
52 views

### Is there a limit to the size of problems that your simulators can run on Qiskit Aqua?

I'm trying to solve QUBO problems using Qiskit QAOA and VQE solvers. However, I have the experience that I can only solve small problems. I tried with both QAOA and VQE and both experience the same ...
• 11
30 views

### How to tune QAOAAnsatz when solution is known to have a certain form?

I'm running QAOAAnsatz in QisKit, and I know that the solution to my problem has a certain form. Namely: ...
107 views

### Combinatorial optimization problems solving using VQE

I'm studying about the variational quantum algorithms and I would like to know about the usage of VQE for solving combinatorial optimization problems. VQE can find the ground state energy of a given ...
• 151
46 views

### Variational Quantum Algorithms for Graph Traversal

I have a combinatorial optimization problem which on a first pass I think boils down to finding a path with a maximal score. The score for a path is computed by an auxiliary function. Are there near-...
• 181
Im trying to get started with QAOA. I tried to program a simple example for testing my understanding. The goal is to maximize $z^TV$ with $V \in \mathbb{R}^{nx1},z \in${$-1,1$}$^n$. I tried ...