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
1answer
54 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
1answer
78 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 ...
1
vote
1answer
36 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
40 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
108 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
30 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
0answers
77 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 ...
7
votes
2answers
93 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 ...
4
votes
0answers
42 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
38 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
49 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
23 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
53 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
50 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
57 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
111 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 ...
4
votes
1answer
64 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
55 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 ...
2
votes
0answers
126 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
60 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
43 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
39 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 ...
4
votes
0answers
50 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
36 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$ ...
4
votes
1answer
60 views

In QAOA, why do we pick the initial Hamiltonian $B$ to be $\sigma_x$ applied to each qubit?

In QAOA 1, why do we pick the initial Hamiltonian $B$ to be $\sigma_x$ applied to each qubit? Would it be possible to pick $B$ to be an application of $\sigma_z$'s instead? Then $C$ and $B$ would be ...
1
vote
2answers
66 views

Quantum Approximate Optimization Algorithm for $p=1$

I was running instances of $3$-regular graphs with small number of vertices on Qiskit, and for $p=1$ the algorithm was giving always the exact solution for the MaxCut problem, after optimizing the ...
2
votes
1answer
56 views

Optimum Solution calculation for QAOA

In QAOA, for the MaxCut problem, one tries to find a good ratio, as close to 1 as possible, of $\epsilon = \frac{C_{approx}}{C_{opt}}$, where $C_{approx}$ is the approximate value of the cost function ...
2
votes
0answers
37 views

How to implement the Mixer of Quantum Alternating Operator Ansatz for Max-Independent-Set

I am trying to implement the Mixer of the Max-Independent Set from The Quantum Alternating Operator Ansatz. From this paper: https://arxiv.org/pdf/1709.03489.pdf in Chapter 4.2 page 15 to 17. For ...
2
votes
1answer
54 views

Papers on classical optimization in QAOA

Are there any papers on the classical optimization part of QAOA? What is the most efficient method now? And how is the classical optimization classified?
2
votes
1answer
132 views

How to solve QUBO problems in Q#?

Short version: I'm trying to solve a traveling salesman problem very similar to the traveling Santa example here: http://quantumalgorithmzoo.org/traveling_santa/, which is also included in the samples ...
4
votes
1answer
205 views

QUBO, Ising Hamiltonians and VQA

I understand that usually the combinatorial optimisation problems are turned into QUBO, which has a very simple mapping to Ising Hamiltonians. Ising Hamiltonians in turn have the desired properties of ...
1
vote
1answer
58 views

An effective way to submit all the jobs for VQE/QAOA at a time to an IBMQ machine?

In Qiskit, I am solving a VRP for 5 nodes and it creates 20 variables for a QUBO. It runs in a 65 qubit machines (any machine below that many fails). Now, in such a typical solvers for optimization (...
3
votes
1answer
96 views

Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?

Quantum annealers are single purpose machines allowing to solve quadratic unconstrained binary optimization (QUBO) problems. QUBO problems have following objective function: $$ F=-\sum_{i<j}J_{ij}...
0
votes
1answer
105 views

Custom Mixer for QAOA: Error 'Operator' object has no attribute 'primitive_strings'

I like to use as custom Mixer Hamiltonian for solving the TSP using QAOA. The mixer and cost hamiltonians are described here: https://arxiv.org/pdf/1709.03489.pdf - Chapter 5.1. Therefore I need to ...
3
votes
1answer
103 views

How does the classical optimization of the angles $\gamma$ and $\beta$ in QAOA work?

I have been trying to implement QAOA with classical optimization of the angles $\gamma$ and $\beta$, but I I'm failing at the classical part. In paper Quantum Approximate Optimization Algorithm: ...
1
vote
0answers
27 views

How to construct Hamiltonian for combinatorial optimization problems and then convert into Pauli basis?

Suppose I have a portfolio optimization problem where I have to minimize, $$qx^T\sum x - \mu^Tx$$ where q is the maximum risk and x is {0,1}^n and $\mu$ are the expected returns. Now I have to convert ...
2
votes
1answer
68 views

Quantum Circuit Optimization with Machine Learning [closed]

I read some paper about Quantum Circuit Optimization but I am on a low level. And have some experience in ML. But what I don't understand is it possible that ML can help to optimize Quantum Circuits ...
1
vote
0answers
57 views

Deriving Expression For QAOA Optimal Trial State Parameters

I am going through the QAOA section in the Qiskit Textbook - QAOA and am stuck in one of the steps. In section 5.2, the method for getting the Optimal Trial State Parameters are discussed. I do not ...
1
vote
1answer
83 views

What is meant by “local minimum” in QAOA?

I am trying to understand what exactly happens in QAOA. I am reading this blog which says, We would be just repetitively applying $U_C$. But once we got into a state which is the eigenstate of $H_C$ ...
0
votes
1answer
112 views

How to do the direct evaluation by hand in QAOA algorithm

In QAOA algorithm, for $p=1$ layer of gates and at most degree $d=3$, the expectation value can be calculated by hand. I think I can convince myself the idea of commutability. In this qiskit example, ...
3
votes
1answer
78 views

What is the implication of locality in QAOA?

Suppose I am solving the TSP formulated as a QUBO problem using QAOA. I understand from the original paper that there is a parameter $p$ which sets the number of steps used in the alternating ansatz. ...
2
votes
1answer
127 views

Why do we transform a Boolean variable into a a Pauli Z matrix

Under Qiskit QAOA's tutorial (https://qiskit.org/textbook/ch-applications/qaoa.html), the authors specify that a cost function $C(x)$ representing the optimization objective of a Binary Combinatorial ...
4
votes
1answer
57 views

Resource recommendation on quantum simulations

I would like to know more about quantum simulations, so as to start on a few standard physical models (maybe particle in a box, harmonic oscillator, etc.) and then build up on more complex things. But ...
0
votes
0answers
59 views

QAOA with Qiskit: Is the initial state affected by the noise model?

I'm doing a simulation of the QAOA algorithm with noise via the QAOA class of Qiskit 0.19. Here's (part of) my code: ...
1
vote
1answer
82 views

Evaluated Standard deviation during QAOA/VQE optimization is always zero. Qiskit 0.19

I'm using qiskit 0.19.1, and I'm doing some simulation of QAOA, using the aqua class QAOA. I use a callback function in my program to see energy and std during optimization, but the evaluated standard ...
1
vote
0answers
34 views

Is there a limit to the size of problems that your simulators can run on Qiskit Aqua?

I'm trying to solve QUBO problems using Qiskit QAOA and VQE solvers. However, I have the experience that I can only solve small problems. I tried with both QAOA and VQE and both experience the same ...
0
votes
1answer
292 views

VQE for Beginners : Using Tutorial and Cirq

I have been following this tutorial: https://dkopczyk.quantee.co.uk/vqe/ I am using Cirq to try to teach myself VQE, replicate their results, and also try to understand more about ansatz for ...
3
votes
1answer
73 views

QAOA Belongs into VQE or the other way around?

I have been reading a couple of papers in the arxiv and wanted to get a clarification regarding the relation between these two methods; is one a subset of the other?
2
votes
1answer
65 views

What does the maximum of a Hamiltonian means (in a particular paper)?

In the paper Quantum Observables for continuous control of the Quantum Approximate Optimization Algorithm via Reinforcement Learning, an Hamiltonian is defined in order to solve the MAXCUT problem : $...
2
votes
1answer
105 views

What does the notation $U(B,\beta) = \prod_{j =1}^n e^{-i \beta \sigma_j^x} $ mean in the context of QAOA?

In the article Quantum Observables for continuous control of the Quantum Approximate Optimization Algorithm via Reinforcement Learning, the following notation is used to describe an Unitary operation ...