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
3
votes
1
answer
169
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 ...
- 39
2
votes
2
answers
221
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 ...
- 141
3
votes
0
answers
73
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?
...
- 519
3
votes
1
answer
70
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}
...
- 519
2
votes
1
answer
159
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 ...
- 45
2
votes
1
answer
234
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/...
- 519
4
votes
0
answers
211
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 ...
- 63
6
votes
1
answer
354
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-...
- 291
3
votes
1
answer
464
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 ...
- 61
4
votes
0
answers
885
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 ...
- 155
2
votes
1
answer
250
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} {\...
- 63
2
votes
1
answer
286
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 ...
- 519
4
votes
1
answer
185
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 ...
- 155
6
votes
0
answers
104
views
In QAOA why do we need $m \log(m)$ repetitions 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 ...
- 519
3
votes
1
answer
171
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$ ...
- 519
4
votes
1
answer
156
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 ...
- 456
1
vote
2
answers
205
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 ...
- 121
2
votes
1
answer
142
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 ...
- 121
2
votes
0
answers
94
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 ...
- 519
3
votes
1
answer
98
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?
- 519
2
votes
1
answer
344
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 ...
- 21
9
votes
1
answer
2k
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 ...
- 279
1
vote
1
answer
287
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 (...
5
votes
1
answer
495
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}...
- 13.6k
0
votes
1
answer
671
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
4
votes
1
answer
459
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: ...
- 519
1
vote
0
answers
90
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
1
answer
156
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 ...
- 141
2
votes
0
answers
135
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 ...
- 21
1
vote
1
answer
226
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$ ...
- 53
2
votes
1
answer
292
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, ...
- 173
3
votes
1
answer
142
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. ...
- 636
2
votes
1
answer
292
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
1
answer
126
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 ...
- 818
1
vote
0
answers
132
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:
...
- 33
1
vote
1
answer
178
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 ...
- 33
1
vote
0
answers
52
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 ...
- 11
0
votes
1
answer
628
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 ...
- 993
3
votes
1
answer
188
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?
- 993
2
votes
1
answer
116
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 :
$...
- 563
2
votes
1
answer
145
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 ...
- 563
1
vote
1
answer
143
views
VQE with error dim. mismatch using qiskit.aqua.vqe
when i try to call the VQE from qiskit I get an error of dimmismatch. The input matrix is of a 16x16 shape and I could not find out what where I introduce the error. In the picture The input matrix ...
- 13
3
votes
1
answer
352
views
QAOA for MaxCut - Algorithm motivation
In the QAOA algorithm for MaxCut, the authors construct a very specific scheme where the qubits (corresponding to the vertices of the graph) are transformed using a sequence of unitaries
$$|\gamma, \...
- 2,597
3
votes
0
answers
115
views
Quantum algorithms, combinatorial optimization, and approximation bounds
Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches.
In particular, they ...
- 1,046
8
votes
1
answer
442
views
Is there a mistake in the VQE Ansatz in Cirq's tutorial?
I have been going through Cirq's VQE background tutorial and after examining the Ansatz it seems to me that the only layer that actually affects the final measurement is the rot_x_layer. The other ...
- 138
16
votes
1
answer
3k
views
Is VQE a class of algorithms or a specific algorithm?
Is VQE a class of algorithms or a specific algorithm? For example, is QAOA a VQE or is VQE an algorithm distinct from QAOA that solves the same class of problems?
If VQE is a specific algorithm, what ...
- 713
2
votes
1
answer
282
views
QAOA Maxcut for larger qubits
I am using QAOA to solve maxcut problem. It takes a very long time to simulate 10 qubits and I never get the results. Is there a way to simulate faster for larger qubit?
Here is my code
...
- 21
1
vote
1
answer
520
views
Backend Warning: The skip Qobj validation does not work for IBMQ provider. Disable it
I am using QAOA to solve the max-cut problem. On my machine, 10 qubits already takes a minute or two to simulate. I'm hoping that the ibmq-qasm-simulator could simulate 32 qubits faster than my laptop ...
- 339
1
vote
1
answer
283
views
How to understand run_algorithm() inputs in qiskit
I'd like to better understand the Max-Cut algorithm from the qiskit tutorials. Particularly, the run_algorithm function inputs. The inputs are two dictionaries, but I can't find any documentation or ...
- 339
3
votes
1
answer
116
views
How does the fact that the output of a quantum circuit cannot be efficiently simulated classically help for optimisation?
This question refers principally to the article where for a low-depth circuit QAOA, the output cannot be efficiently simulated classically. I am wondering how this kind of quantum supremacy matters ...
- 4,644