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
0answers
10 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 ...
1
vote
0answers
19 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 ...
0
votes
1answer
47 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 - ...
0
votes
1answer
46 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 ...
2
votes
1answer
66 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
vote
0answers
19 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 ...
2
votes
0answers
65 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\,\,...
1
vote
1answer
81 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
1answer
46 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
2answers
119 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
1answer
41 views

Pack Header Error when using QAOAProgram [closed]

I want to use QAOAProgram from Qiskit in the following way: ...
3
votes
0answers
27 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
2answers
111 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 ...
7
votes
1answer
187 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
0answers
54 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 ...
3
votes
1answer
108 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 ...
3
votes
1answer
54 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 ...
4
votes
0answers
39 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
1answer
48 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'...
4
votes
1answer
312 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. ...
3
votes
1answer
176 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. ...
0
votes
0answers
29 views

QAOA Circuit for MWIS

Hi thanks for taking a quick look! I’ve got a question of how weights are implemented in the angles for gates in the QAOA. I'm trying to solve the Maximum Weighted Independent Set Problem This is the ...
1
vote
1answer
56 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 ...
1
vote
1answer
49 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$...
1
vote
1answer
73 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 ...
0
votes
1answer
52 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\...
3
votes
2answers
126 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 ...
2
votes
2answers
166 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 ...
2
votes
1answer
85 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 ...
1
vote
0answers
49 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
2answers
352 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 ...
0
votes
0answers
41 views

Interpret graph nodes as qubits

I am trying implement MAXCUT using QAOA. I have a graph with edges defined by an edges set. My edges set looks a bit like this: ...
4
votes
1answer
161 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 ...
8
votes
2answers
150 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 ...
6
votes
1answer
82 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 ...
3
votes
1answer
80 views

Initial state definition for QAOA

There are a few options already discussed and suggested how to pass the initial state to the QAOA module. I tried all but no one works in my case. Maybe, there are any other ideas? So, I created the ...
2
votes
2answers
100 views

Quantum Machine Learning in NISQ era

I know that quantum algorithms can be useful for machine learning ("ML") methods, and vice versa. For example if we use QAOA we can use for the optimization part different types of ML ...
2
votes
0answers
39 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? ...
3
votes
1answer
62 views

Is $\gamma \in [0,2 \pi]$ or $\gamma \in [0,\pi]$ in $CU1(2\gamma)_{(i,j)} $?

When wanting to find the groundstate of this Hamiltonian with QAOA: \begin{equation} H_{C} =\sum_{i }^{n}(1 - Z_{i})/2 + \sum_{\{i,j\}\in \overline{E} } - 2(1 - Z_{i})(1 - Z_{j})/4 \end{equation} ...
2
votes
1answer
73 views

Qiskit: getting QAOA expectation

Suppose I run the Qiskit's QAOA algorithm. qaoa = QAOA(operator=qubit_operator, p=p, optimizer=optimizer) result = qaoa.run(quantum_instance) There is a built-in ...
2
votes
1answer
82 views

How to use Initial States in Qiskits QAOA?

The class QAOA from qiskit: https://qiskit.org/documentation/stubs/qiskit.aqua.algorithms.QAOA.html has the parameter initial_state from the type InitialState. https://qiskit.org/documentation/apidoc/...
3
votes
0answers
134 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 ...
5
votes
1answer
93 views

Why QAOA with $p \rightarrow \infty $ gives the optimal solution?

In the QAOA paper, it is shown that the optimal value of the p-ansatz $M_p$ converges to $\max_z C(z)$ as $p \rightarrow \infty$ on page 10. The proof is to relate to QAOA by considering the time-...
3
votes
1answer
85 views

Can QAOA solve a constraint optimization problem?

Can QAOA solve a constraint binary optimization problem? QAOA is short for Quantum Approximate Optimization Algorithm. I read the information https://qiskit.org/textbook/ch-applications/qaoa.html. But ...
3
votes
0answers
321 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 ...
2
votes
1answer
103 views

Decomposition of 2-qubit Hamiltonian into standard gate set for QAOA

I try to decompose ansatz into gate set in order to create a circuit in qiskit for QAOA algorithm. I don't understand how represent parametrized 2 qubit ansatz as circuit. $ H{_B} = \sum_{j=1}^{n} {\...
2
votes
1answer
76 views

Why does the problem Hamiltonian of QAOA always consist of $Z$ and $I$ gates?

I noticed that in QAOA the problem hamiltonian always consists of $Z$ and $I$ gates. But isn't QAOA a form of Adiabatic Programming? Where the idea is just to go from one ground state to another? Does ...
4
votes
1answer
61 views

Classical optimisation of angles in QAOA for TSP gets stuck in local minima?

I have been trying to implement a QAOA for solving a traveling salesman problem (TSP) using qulacs and python. However, even for ...
5
votes
0answers
54 views

In QAOA why do we need $m \log(m)$ repititions 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 ...
2
votes
1answer
73 views

To find the best angles in QAOA why we do not optimize over a maximum ofall shots instead of a mean?

When finding the best angles for QAOA we optimize over $F_{p}(\beta , \gamma) = \langle \psi_p(\gamma,\beta)|C|\psi_p(\gamma,\beta)\rangle $. In each optimization step we simulate the circuit $m$ ...