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).
153
questions
2
votes
2
answers
504
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:
...
- 23
3
votes
1
answer
124
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 ...
- 31
2
votes
0
answers
150
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
3
votes
2
answers
478
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 ...
- 271
4
votes
0
answers
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
2
votes
1
answer
145
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 ...
- 271
4
votes
0
answers
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}
...
- 83
4
votes
1
answer
406
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 ...
- 231
1
vote
1
answer
239
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 ...
- 231
3
votes
1
answer
392
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 ...
- 485
3
votes
1
answer
296
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\...
- 671
4
votes
0
answers
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
1
vote
0
answers
75
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 ...
- 615
0
votes
0
answers
191
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
2
votes
1
answer
178
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 ...
- 179
6
votes
1
answer
1k
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 ...
- 478
12
votes
1
answer
402
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 ...
- 303
3
votes
1
answer
199
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 ...
- 53
3
votes
1
answer
285
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
284
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 - ...
- 53
0
votes
1
answer
201
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,343
2
votes
1
answer
416
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,343
1
vote
0
answers
82
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
4
votes
0
answers
137
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\,\,...
- 231
1
vote
1
answer
211
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
0
votes
1
answer
77
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&...
- 111
2
votes
2
answers
316
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 ...
- 75
1
vote
1
answer
71
views
Pack Header Error when using QAOAProgram [closed]
I want to use QAOAProgram from Qiskit in the following way:
...
- 53
4
votes
0
answers
56
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,515
1
vote
2
answers
767
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 ...
- 33
13
votes
1
answer
905
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,515
1
vote
0
answers
100
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 ...
- 311
4
votes
1
answer
889
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 ...
- 1,031
4
votes
1
answer
374
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 ...
7
votes
2
answers
161
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 ...
- 13.6k
2
votes
1
answer
117
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'...
8
votes
1
answer
3k
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. ...
- 1,031
4
votes
1
answer
1k
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.
...
1
vote
1
answer
80
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 ...
- 209
2
votes
1
answer
65
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$...
- 390
1
vote
1
answer
371
views
How to create an observable: 'Identity \tensor Pauli gate' in Cirq
I am working on an implementation of the RQAOA algorithm on the Maxcut problem in Cirq.
My graph G has n vertices. And after running a QAOA circuit with n qubits I obtain a state gammabeta (a vertical ...
- 13
0
votes
1
answer
123
views
Best way to compute $\langle a|B|a \rangle$ in Cirq, where a is a state obtained running circuit A. And B is a different Quantum Circuit
I am implementing RQAOA in Cirq.
After running regular QAOA to find an optimal state a (This I have done successfully).
I need to calculate $\langle a|Z_iZ_j|a\...
- 13
4
votes
2
answers
325
views
Statevector Simulation of QAOA always finds exact solution
My question is simple: does applying QAOA with a statevector simulation always result in a perfect solution?
I'm trying to calculate the best $\gamma$ & $\beta$ that solve certain problems but my ...
- 209
3
votes
2
answers
396
views
What exactly happening in QAOA in a general way?
So I know that in QAOA we have the two hamiltonians. Mixer and Cost Hamiltonian.
Lets start:
First we have our Qubits which get in the Superposition if we add the Hadamard Gate.
Then we have the both ...
- 141
2
votes
1
answer
132
views
IBM Qiskit QAOA gate implementation question
In section $5.2$ of the QAOA chapter in Qiskit textbook, section $5.2$,
state preparation uses the gate $U_{k,l}(\gamma) = e^{\frac{i \gamma}{2} (1-Z_k Z_l)}$. Later, in section $5.3$, this gate is ...
- 105
1
vote
0
answers
83
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 ...
2
votes
2
answers
2k
views
Qiskit: Taking a QUBO matrix into `qubit_op'
I'm trying to solve the maximum independent set problem using Qiskit and the QAOA.
I've a nice QUBO Matrix for this simple path graph:
as so:
My question is, how do I convert this into a general ...
- 209
5
votes
1
answer
891
views
Solving higher-order (unconstrained) binary optimization problems with QAOA without quadratization
I am aware that it's possible to use QAOA to solve QUBO problems. However, I've recently seen some sources mentioning the possibility of solving HOBO/HUBO problems using QAOA as well [1][3].
While I ...
- 51
8
votes
2
answers
757
views
Why does QAOA achieve quantum supremacy in an algorithmic sense?
In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15):
"If [...] the QAOA outperforms all known classical algorithms ...
- 485
6
votes
1
answer
541
views
Properties of QAOA
The QAOA algorithm consists of two elements:
The outer loop, basically a classical optimization algorithm
The quantum circuit, taking $2p$ parameters (where $p$ is the number of layers, where each ...
- 485