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
3
votes
0answers
31 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} ...
2
votes
1answer
65 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 ...
1
vote
1answer
57 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 ...
1
vote
1answer
67 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
1answer
64 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\...
2
votes
0answers
26 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
vote
0answers
43 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 ...
0
votes
0answers
59 views

Correct implementation of Qiksit 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
1answer
42 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 ...
2
votes
1answer
116 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 ...
9
votes
1answer
155 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
1answer
80 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
38 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
58 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
71 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
120 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
25 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
82 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
104 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
53 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
149 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
52 views

Pack Header Error when using QAOAProgram [closed]

I want to use QAOAProgram from Qiskit in the following way: ...
3
votes
0answers
35 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
199 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 ...
9
votes
1answer
272 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
61 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
255 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
1answer
74 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
49 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
58 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
512 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. ...
4
votes
1answer
306 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
30 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
60 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
50 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
119 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
56 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
154 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
207 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
95 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
53 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
501 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
51 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
257 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
204 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
103 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
96 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
134 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
44 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} ...