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).
47
questions with no upvoted or accepted answers
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
0
answers
71
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
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
134
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
0
answers
57
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 ...
- 31
3
votes
0
answers
66
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 ...
- 674
3
votes
1
answer
240
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
...
- 31
3
votes
0
answers
100
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}
...
- 73
3
votes
0
answers
76
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,313
3
votes
0
answers
124
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\,\,...
- 101
3
votes
0
answers
44
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,455
3
votes
0
answers
67
views
Is the problem Hamiltonian in QAOA and AQC always a phase Hamiltonian?
In QAOA and AQC the problem Hamiltonian is always a Phase Hamiltonian (meaning only phases are added)
Is that part of the QAOA and AQC definition or it is only used because it is convenient and work?
...
- 519
3
votes
0
answers
198
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 ...
- 53
3
votes
0
answers
860
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 ...
- 145
3
votes
0
answers
105
views
Quantum algorithms, combinatorial optimization, and approximation bounds
Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches.
In particular, they ...
- 1,036
2
votes
0
answers
23
views
Implementing Adiabatic Grover Search via QAOA
I am reading the paper Grover Search Inspired Alternating Operator Ansatz of Quantum Approximate
Optimization Algorithm for Search Problems. The paper proposes running the Adiabatic Grover Search ...
- 181
2
votes
0
answers
35
views
Can we easily find the ground states for one-dimensional ANNNI-like Ising models?
The Hamiltonian for a simple one-dimensional Ising model on a finite (linear) chain of $L$ spin-half particles might be:
$$H = -J \sum_{i=0}^{L-1} \sigma_i^z \sigma_{i+1}^z.\tag{1}$$
The interactions ...
- 10.1k
2
votes
0
answers
59
views
Custom Mixer for QAOA for Graph Coloring, where to start?
I am trying to implement QAOA for graph coloring with hard constraints. In this paper, eq. 9 a custom mixer is proposed, is looks like this:
$B_{ui} = \frac{1}{2^{l + 1}}(X_{u0}X_{u1} + Y_{u0}Y_{u1}) \...
2
votes
0
answers
138
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
2
votes
1
answer
357
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 ...
- 445
2
votes
0
answers
84
views
How to implement the Mixer of Quantum Alternating Operator Ansatz for Max-Independent-Set
I am trying to implement the Mixer of the Max-Independent Set from The Quantum Alternating Operator Ansatz.
From this paper: https://arxiv.org/pdf/1709.03489.pdf in Chapter 4.2 page 15 to 17.
For ...
- 519
2
votes
0
answers
124
views
Deriving Expression For QAOA Optimal Trial State Parameters
I am going through the QAOA section in the Qiskit Textbook - QAOA and am stuck in one of the steps. In section 5.2, the method for getting the Optimal Trial State Parameters are discussed. I do not ...
- 21
1
vote
0
answers
32
views
Building a problem unitary circuit for QAOA on Qiskit
I am trying to build a circuit for QAOA that solves a Traveling Salesman's Problem, which can be represented as a complete graph with 4 nodes. After formulating the problem as a QUBO and mapping it ...
- 159
1
vote
1
answer
40
views
How are edge weights "loaded" in the problem hamiltonian when solving TSP with QAOA?
I've come across several of the QAOA tutorials, and yet I'm afraid I haven't found any explanation on this. According to the Qiskit tutorial on QAOA, the cost function for the target problem has a ...
- 159
1
vote
0
answers
45
views
IS my QUBO too big for QAOA using IBM Quantum computer?
On qiskit, I have defined a QUBO, called qp as follows:
...
- 83
1
vote
0
answers
35
views
Link between AQC and QAOA
I try to understand precisely the link between AQC and QAOA, through the Trotter-Suzuki formula.
A similar question is Derivation of QAOA from AQC, but I was asked by moderators to post my question ...
- 73
1
vote
0
answers
28
views
'Continuous' (Classical) Cost function for QAOA
I have some combinatorial optimization problems which I would like to analyze using QAOA. These problems are coming from various applications in scientific computing such as solving PDEs. Some of ...
- 181
1
vote
0
answers
65
views
QAOA algorithm from qiskit.algorithms.minimum_eigensolvers sends jobs without stopping
I don't know why the code keeps sending jobs. The code is:
...
1
vote
0
answers
36
views
Qiskit: The parameters of the circuits constructed by QAOAAnsatz will change after decomposition and transpilation
When I submit a parametrized circuit as an input for the mixed operator in QAOAAnsatz, some strange results appear.
For example, when I submit a parametrized ...
- 11
1
vote
1
answer
85
views
Calculating state fidelity and space complexity of Minimum Eigen Optimizers (VQE, QAOA and Grover Optimizer) in qiskit
I'm a beginner in using Qiskit and my Computer Science background is not extensive. But I understand the Quantum Physics aspects of it relatively well.
I solved a QUBO problem in Qiskit using VQE (...
1
vote
0
answers
118
views
Interpreting VQE and QAOA based solutions in portfolio optimization
I am going through portfolio optimization using Qiskit. It really looks interesting. The module has both VQE and QAOA algorithms for optimizing the portfolios.
In the VQE based solution the ...
- 31
1
vote
0
answers
29
views
Error analysis on the approximation of an adiabatic evolution operator by a QAOA circuit
I would like to know what would be the approximation error of a QAOA circuit.
Suppose we have time-dependent Hamiltonian $H(t) = (1 - s(t))H_{init} + s(t)H_{prob}$ where $H_{init}$ in an initial ...
- 2,339
1
vote
0
answers
68
views
Confusion about the objective function of VQEs and QAOAs
I am a bit puzzled on how the objective function of the VQEs and QAOAs. Of course, the parametrised state is constructed differently in these two algorithms but they do share a common objective to be ...
- 585
1
vote
0
answers
64
views
How can a Mixer Hamiltonian restrict the search within a subspace of the statespace in QAOA?
I understand that the role of the Mixer Hamiltonian prevents the creation of a constant function where there is nothing to be minimized.
I would like to understand from a mathematical perspective how ...
- 41
1
vote
1
answer
205
views
QAOA Optimization
I want to use historical data for 5 stocks from YahooFinance and then calculate mean vector and covariance matrice, so I can optimize them with QAOA. Anyone know what is wrong with this code:
- 29
1
vote
0
answers
91
views
How to calculate Alpha and Beta values for QAOA Max-cut problem manually?
I'm new to Quantum Computing. I came across solving the Max-cut problem using QAOA. For example, if I have a $U3$ gate with parameters $U3(0,0, \gamma_{XYZ})$ gamma parameter at $p=X$ between logical ...
- 301
1
vote
0
answers
78
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 ...
1
vote
0
answers
81
views
How to construct Hamiltonian for combinatorial optimization problems and then convert into Pauli basis?
Suppose I have a portfolio optimization problem where I have to minimize,
$$qx^T\sum x - \mu^Tx$$
where q is the maximum risk and x is {0,1}^n and $\mu$ are the expected returns.
Now I have to convert ...
1
vote
0
answers
48
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
0
votes
0
answers
35
views
Converting Ising Hamiltonian to a Circuit in Qiskit
I tried to solve a 2-node TSP (travelling salesman problem) by implementing QAOA on Qiskit. The graph looks like:
Then I used the related Qiskit functions to convert the graph to the QUBO and map it ...
- 159
0
votes
0
answers
24
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:
...
- 61
0
votes
0
answers
54
views
How to change the simulator used by Qiskit's `QAOA` (or get around the "Maximum allowed dimension exceeded" error)?
I'm running MinimumEigenOptimizer with QAOA on a large quadratic program:
...
- 33
0
votes
0
answers
91
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 ...
- 141
0
votes
0
answers
34
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
0
votes
0
answers
18
views
Maximize the Sum of absolut Vector elements with QAOA
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 ...
- 23
0
votes
0
answers
177
views
Correct implementation of Qiskit QAOA
I've been dealing with a QAOA implementation of a QUBO problem. In order to do this, I converted my QUBO matrix to a QuadraticModel. Once done, I have used ...
- 179
0
votes
0
answers
125
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:
...
- 23