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
1 vote
1 answer
57 views

Implementing QAOA Hamiltonian for MAX-3-SAT in Qiskit

I have read about how QAOA is used to tackle the MAX-CUT problem and wanted to test my understanding by trying to implement some code to approximate the MAX-3-SAT problem. To do so, I considered the ...
1 vote
1 answer
23 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 (...
2 votes
0 answers
86 views

How to implement Qiskit QAOA code on a real quantum computer?

I'm trying to run the QAOA code from Qiskit (https://qiskit.org/textbook/ch-applications/qaoa.html) on a real quantum computer. However, it doesn't work. Here starts my code: ...
  • 21
1 vote
0 answers
52 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
17 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 ...
  • 1,161
3 votes
0 answers
46 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 ...
3 votes
1 answer
100 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
2 votes
1 answer
93 views

For the same operator, when I use qiskit's VQE and QAOA solutions, the results are completely different

Specifically, I can't get the correct result using QAOA,A total of 6 qubits were used in this work,this is part of my code using VQE and QAOA localsim = BasicAer.get_backend('qasm_simulator') ...
  • 21
2 votes
1 answer
138 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 ...
  • 515
3 votes
2 answers
115 views

qiskit qaoa.compute_minimum_eigenvalue

I am having some trouble running the compute_minimum_eigenvalue method from qiskit's QAOA: the documentation states that one ...
0 votes
1 answer
40 views

Validating existing QAOA, deprecated solutions on qiskit

I'm currently evaluating a static QC, QML and QAOA approach to solving a combinational problem. My solution with the static QC and QML approach is finished, and all data has been collected. Now, the ...
  • 147
2 votes
2 answers
229 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: ...
0 votes
0 answers
45 views

Find minimum eigenvalue of an Ising Hamiltonian combined with Error Mitigation

I am currently working on a variation of the Traveling Salesman Problem. For which I use the QUBO(Quadratic Unconstrained Binary Optimization). Within Qiskit there are potent functions to obtain the ...
2 votes
1 answer
53 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
62 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
0 answers
55 views

Given a cost Hamiltonian, how to determine number of qubits required for running QAOA?

Say I have a cost Hamiltonian for an optimization problem which involves an objective function, and constraints (in particular, section III of this paper 1, on page 3). I’d like to determine the ...
  • 121
3 votes
2 answers
200 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 ...
4 votes
0 answers
78 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 ...
2 votes
1 answer
75 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 ...
0 votes
0 answers
102 views

Hardware efficient ansatz versus Alternating Layered Ansatz

I'm reading a paper Cost function dependent barren plateaus in shallow parametrized quantum circuits. There they introduce what is called Alternating Layered Ansatz (ALA). It is said that: The ...
  • 249
3 votes
0 answers
66 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
134 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 ...
  • 81
1 vote
1 answer
144 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 ...
  • 81
1 vote
1 answer
202 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
150 views

QAOA calculation expectation value

Given the QAOA circuit $U(\vec\gamma, \vec\beta)$, associated to some cost hamiltonian $H_C$, and evolving the state $|0\rangle^{\otimes n}$ into $|\vec\gamma, \vec\beta\rangle = U(\vec\gamma, \vec\...
  • 715
3 votes
0 answers
44 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,283
1 vote
0 answers
62 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 ...
  • 515
0 votes
0 answers
129 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 ...
2 votes
1 answer
99 views

How do we calculate the offset in a QUBO formulation?

I am aware that for a quadratic optimization problem, we are required to minimize $y$ where $y = x^t Q x$ where $x$ is a column vector of binary variables and $Q$ is a QUBO matrix. I have the ...
3 votes
1 answer
473 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 ...
  • 438
11 votes
1 answer
240 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 ...
3 votes
1 answer
136 views

How to use Clifford Data Regression for the MaxCut Problem

i read about Clifford Data Regression in https://arxiv.org/pdf/2005.10189.pdf. If I have understood this correctly, then one receives the mitigated expected value of an observable from CDR. For the ...
  • 43
3 votes
1 answer
135 views

What is the relationship between the mixing operators and initial states found in QAOA and Quantum Annealing?

In many papers, the QAOA is shown to be intimately related to Quantum Annealing/Quantum Adiabatic Algorithm/Adiabatic Quantum Optimization. The mixing operator in the QAOA is described by Hadfield as ...
  • 41
0 votes
1 answer
133 views

RZZ calculation: Why does the equation and the circuit correspond?

i found this tutorial about MaxCut and QAOA from pennylane and i do not understand how the equation and the circuit should be equal. When i do the math i come to this conclusion: (result of CNOT - ...
  • 43
0 votes
1 answer
109 views

How to calculate the approximation ratio of QAOA?

In order to evaluate the QAOA circuit, we need to compute the approximation ratio, which is the expectation value of QAOA circuit divided by the best solution. My question is, how to find the best ...
  • 1,283
2 votes
1 answer
237 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 ...
  • 1,283
1 vote
0 answers
36 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
3 votes
0 answers
97 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\,\,...
  • 81
1 vote
1 answer
150 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:
0 votes
1 answer
58 views

Cirq QAOA Tasks returns "iteration over a 0-d array" error

I'm trying to understand how to use Recirq for QAOA, and I tried to run the notebook for tasks: https://quantumai.google/cirq/experiments/qaoa/tasks. But it gives a "iteration over a 0-d array&...
2 votes
2 answers
195 views

Initial state for QAOA

I'm learning about QAOA and I got curious about how they choose initial state. They somehow decided to choose initial state as equal superposition of all possible state and I wonder that there is any ...
1 vote
1 answer
58 views

Pack Header Error when using QAOAProgram [closed]

I want to use QAOAProgram from Qiskit in the following way: ...
  • 43
3 votes
0 answers
39 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 vote
2 answers
349 views

How to build a QAOA Ansatz

I saw there is a qiskit package called "QAOAAnsatz" https://qiskit.org/documentation/stubs/qiskit.circuit.library.QAOAAnsatz.html. But I didn't find out any tutorial related, so I have no ...
11 votes
1 answer
483 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 ...
1 vote
0 answers
73 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 ...
  • 191
3 votes
1 answer
549 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 ...
4 votes
1 answer
187 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 ...
5 votes
0 answers
71 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 ...
2 votes
1 answer
82 views

QAOA not returning solution for simple clustering problem

I am following University's of toronto QML course and there's a section where QAOA is applied to cluster a set of vectors by mapping the clustering problem into a Maxcut problem. Unfortunately qiskit'...