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
0 votes
0 answers
7 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 ...
user avatar
  • 196
3 votes
0 answers
35 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 ...
user avatar
2 votes
1 answer
56 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 ...
user avatar
  • 21
2 votes
1 answer
84 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') ...
user avatar
  • 21
2 votes
1 answer
77 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 ...
user avatar
  • 505
3 votes
2 answers
88 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 ...
user avatar
0 votes
1 answer
31 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 ...
user avatar
  • 147
2 votes
2 answers
120 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: ...
user avatar
0 votes
0 answers
32 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 ...
user avatar
2 votes
1 answer
40 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 ...
user avatar
2 votes
0 answers
51 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 ...
user avatar
  • 21
2 votes
0 answers
44 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 ...
user avatar
  • 121
3 votes
2 answers
150 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 ...
user avatar
4 votes
0 answers
63 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 ...
user avatar
2 votes
1 answer
72 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 ...
user avatar
0 votes
0 answers
64 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 ...
user avatar
  • 249
3 votes
0 answers
48 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} ...
user avatar
4 votes
1 answer
102 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 ...
user avatar
  • 81
1 vote
1 answer
127 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 ...
user avatar
  • 81
1 vote
1 answer
148 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 ...
user avatar
3 votes
1 answer
110 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\...
user avatar
  • 715
2 votes
0 answers
40 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 ...
user avatar
  • 1,263
1 vote
0 answers
57 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 ...
user avatar
  • 505
0 votes
0 answers
98 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 ...
user avatar
2 votes
1 answer
69 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 ...
user avatar
3 votes
1 answer
329 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 ...
user avatar
  • 438
11 votes
1 answer
215 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 ...
user avatar
3 votes
1 answer
123 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 ...
user avatar
  • 43
3 votes
1 answer
110 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 ...
user avatar
  • 41
0 votes
1 answer
107 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 - ...
user avatar
  • 43
0 votes
1 answer
100 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 ...
user avatar
  • 1,263
2 votes
1 answer
202 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 ...
user avatar
  • 1,263
1 vote
0 answers
32 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 ...
user avatar
  • 41
3 votes
0 answers
91 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\,\,...
user avatar
  • 81
1 vote
1 answer
128 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:
user avatar
0 votes
1 answer
57 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&...
user avatar
2 votes
2 answers
177 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 ...
user avatar
1 vote
1 answer
56 views

Pack Header Error when using QAOAProgram [closed]

I want to use QAOAProgram from Qiskit in the following way: ...
user avatar
  • 43
3 votes
0 answers
37 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 ...
user avatar
1 vote
2 answers
297 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 ...
user avatar
11 votes
1 answer
404 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 ...
user avatar
1 vote
0 answers
69 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 ...
user avatar
  • 181
3 votes
1 answer
456 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 ...
user avatar
4 votes
1 answer
157 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 ...
user avatar
5 votes
0 answers
62 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 ...
user avatar
2 votes
1 answer
75 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'...
user avatar
6 votes
1 answer
986 views

What's the role of mixer in QAOA?

In QAOA algorithm, two terms are being discussed; 1) clause or cost (C) Hamiltonian and 2) mixer consisting of pauli X gates. What is the role of this mixer? Not clear why it comes after the C. ...
user avatar
4 votes
1 answer
506 views

Calculating the ground states of an Ising Hamiltonian on a real quantum computer

I have followed this tutorial and based on it, I've written the following function in qiskit, which can explicitly calculate the ground states of a transverse-field Ising Hamiltonian. ...
user avatar
1 vote
1 answer
65 views

Why do we seek to maximise $F_{p}(\gamma, \beta)=\langle\gamma, \beta|H_{C}| \gamma, \beta\rangle$?

The question is simple: why do we seek to maximise $F_{p}(\gamma, \boldsymbol{\beta})=\langle\gamma, \boldsymbol{\beta}|H_{C}| \gamma, \boldsymbol{\beta}\rangle$? How does maximising this value ...
user avatar
  • 189
2 votes
1 answer
54 views

Is there a matrix whose sum with the canonical Mixing Hamiltonian in Qaoa is proportional to the identity matrix?

Does there exist a Hermitian matrix, $K$ s.t $B^\prime = B + K$ satisfies $(B^\prime)^2 = c\cdot I$, where $B = \sum_{i=1}^{n}\sigma_x^{(i)}$, $\sigma_x^{(i)}$ is the Pauli X matrix acting on qubit $i$...
user avatar