Skip to main content

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

58 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
0 answers
128 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
0 answers
169 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
321 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
179 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
123 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
945 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
0 answers
73 views

Why don't we start evolution with ground state in QAOAnsatz?

The adiabatic theorem states that we can start from an eigenstate, slowly change our Hamiltonian and still remain in the eigenstate. In the vanilla QAOA we start from $|+\rangle^n$, which is the ...
HaraldRudobrody's user avatar
3 votes
0 answers
71 views

qiskit QAOA on Aer GPU giving errors

I am trying to run Qiskit QAOA algorithm on using aer simulator and device GPU. But I am not sure how to give this backend in the QAOA algorithm structure. Here is ...
to_batman's user avatar
3 votes
0 answers
45 views

How to update angles

I am struggling to understand the concept of updating angles in a parameterized algorithm. Assume I have an objective function $x^2+1$ that I want to optimize using QAOA which can handle continuous ...
34341's user avatar
  • 31
3 votes
0 answers
47 views

How can one use QAOA to obtain parameters that approximate the first excited state of the target Hamiltonian?

One can use QAOA to find the ground state and its energy by minimizing the expectation value of a target Hamiltonian (say, $H_T$) with respect to the QAOA ansatz and obtaining optimal parameters ...
Pratham Hullamballi's user avatar
3 votes
1 answer
467 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 ...
Nepomuk Hirsch's user avatar
3 votes
0 answers
80 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? ...
Hannah's user avatar
  • 529
3 votes
0 answers
125 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 ...
Greenstick's user avatar
  • 1,086
2 votes
0 answers
136 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 ...
Alternative7's user avatar
2 votes
0 answers
47 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 ...
user82261's user avatar
  • 191
2 votes
0 answers
48 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 ...
Mark Spinelli's user avatar
2 votes
0 answers
89 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}) \...
Himera Ephemera's user avatar
2 votes
0 answers
178 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 ...
Hirschi's user avatar
  • 21
2 votes
0 answers
100 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 ...
RMistri's user avatar
  • 51
2 votes
0 answers
97 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 ...
Hannah's user avatar
  • 529
2 votes
0 answers
138 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 ...
Vijey's user avatar
  • 21
1 vote
0 answers
21 views

Adiabatic evolution vs QAOA

Attempting to understand some basics here before developing an quantum algorithm. Would of you be able to help clarify the following definitions I attempted to construct which compare the two ...
Qu Bit's user avatar
  • 11
1 vote
0 answers
24 views

Do encoding schemes for variational algorithms apply to annealing methods (e.g. DWave)?

I understand there are some efficient encoding schemes for variational algorithms, that attempt to approximate the variational state using fewer qubits. I'm thinking of 2 papers in particular, which ...
IsalanOnkar's user avatar
1 vote
0 answers
16 views

Can dimensionality reduction be used to simplify data before using an optimization algorithm?

I am attempting to use a quantum algorithm, like a QAOA, to solve an optimization problem. I saw that qPCA can be used to simplify datasets and make them easier to analyze. Can quantum optimization be ...
Mihir Macwan's user avatar
1 vote
0 answers
109 views

How to convert QUBO (with non-zero diagonal elements) to Maxcut?

I want to solve QUBO with non-zero diagonal elements in matrix Q using QAOA. But I want to solve for a large enough problem size (30+ variables) and hence want to divide my circuit into subcircuits. ...
Oleksii's user avatar
  • 21
1 vote
0 answers
54 views

How to run the post processing and return results in QAOA?

As suggested in TranspilerError: 'Number of qubits (40) in QAOA is greater than maximum (30) in the coupling_map' issue. I managed to submit the job to IBM quantum and the circuit runs successfully. ...
Lasal Hettiarachchi's user avatar
1 vote
0 answers
19 views

What is the benefit of using a Multi Angle QAOA?

I am currently doing some research that requires a quantum optimization algorithm. I have been looking at types of quantum algorithms to see which one would be most useful for my problem and ...
Mihir Macwan's user avatar
1 vote
0 answers
68 views

How to solve a QUBO problem by QAOA algorithm with Qiskit Optimization on a real quantum resources/hardware?

I am new to quantum computing, and I am following this tutorial trying to use Qiskit Optimization 0.6.0 to solve a simple quadratic problem by applying QAOA algorithm. As stated in the tutorial, I ...
Chuck's user avatar
  • 21
1 vote
0 answers
58 views

Qiskit bad unitary decomposition

I want to decompose a two-qubit unitary gate $U$, $$U = e^{-i \cdot \frac{t}{2} \cdot Z_1 \cdot Z_2}\,,$$ where $t$ is an angle. I already know the right decomposition but Qiskit gives me an ...
Daniele Trisciani's user avatar
1 vote
1 answer
65 views

Question on efficiency of HOBO Quadratization and other depth reducing techniques

I am having trouble understanding some concepts in Quadratizing a high order polynomial. I am reading the review "Quadratization in Discrete Optimization and Quantum Mechanics" . I would ...
QuantumTheoretical's user avatar
1 vote
1 answer
177 views

Error code 1217, Message: Reduce time between submitting subsequent jobs in a session

I tried running a piece of Qiskit code to minimize a Hamiltonian using QAOA. I tried running the same piece of code that I had used earlier in the IBM Quantum system 'ibm_nairobi' which gave me the ...
Amrita P's user avatar
1 vote
0 answers
85 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 ...
Alternative7's user avatar
1 vote
1 answer
65 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 ...
Alternative7's user avatar
1 vote
0 answers
115 views

IS my QUBO too big for QAOA using IBM Quantum computer?

On qiskit, I have defined a QUBO, called qp as follows: ...
Stéphane's user avatar
1 vote
0 answers
66 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 ...
deb2014's user avatar
  • 191
1 vote
0 answers
48 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 ...
user82261's user avatar
  • 191
1 vote
0 answers
95 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: ...
Mattia Chiurco's user avatar
1 vote
0 answers
66 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 ...
user23270's user avatar
1 vote
1 answer
139 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 (...
Janani Ananthanarayanan's user avatar
1 vote
0 answers
166 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 ...
Rag's user avatar
  • 31
1 vote
0 answers
40 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 ...
MonteNero's user avatar
  • 2,684
1 vote
0 answers
77 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 ...
Marion's user avatar
  • 635
1 vote
0 answers
104 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 ...
Monica's user avatar
  • 311
1 vote
0 answers
88 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 ...
SakibulIslamSazzad's user avatar