21
votes
Accepted
Is VQE a class of algorithms or a specific algorithm?
I view QAOA as an algorithm for solving (approximately) a special class of problems, namely combinatorial problems and VQE as a possible subroutine to QAOA (but not necessarily as in the case of ...
- 959
15
votes
Accepted
What's the role of mixer in QAOA?
Probably the easiest way to understand this is to pretend that the mixer is NOT there and see what happens. So, let's assume you have some initial state $\lvert \psi \rangle = \sum_x \psi_x \lvert x \...
- 510
10
votes
Why exactly are variational algorithms considered promising?
"As far as I understand there aren't many rigorous results on performance of these algorithms, similar to many classic machine learning approaches."
You are correct in that, unlike Grover's ...
10
votes
Accepted
What does the paper "Training Variational Quantum Algorithms Is NP-Hard (Phys. Rev. Lett. 127, 120502)" mean?
The paper doesn't address very much the "fully classical" approach to their problems, so I don't think they are making a judgment one way or another about quantum advantage with VQA. But ...
- 1,251
9
votes
Accepted
Why does QAOA achieve quantum supremacy in an algorithmic sense?
"but for me quantum supremacy would mean that no classical algorithm can exist at all that solves the problem in a better way than a quantum algorithm."
If that were the case, then "...
7
votes
Accepted
What is the difference between QAOA and Quantum Annealing?
One of the advantages, as stated in the paper you linked, is that with QAOA you can increase the precision arbitrarily, whereas QA will only find the solution with probability 1 as $T \to \infty$ ...
- 1,749
7
votes
What exactly happening in QAOA in a general way?
A precursor to the canonical QAOA is the Quantum Adiabatic Algorithm (QAA). Since we want to end up in the ground state of the Cost Hamiltonian ($H_C$) but don't know how to construct it, we exploit ...
- 390
7
votes
Accepted
Calculating the ground states of an Ising Hamiltonian on a real quantum computer
You can definitely run this on a real quantum computer! In your snippet above you mixed circuits and operators. A circuit is only used for the ansatz of your ground state, not for representing the ...
- 2,973
7
votes
Accepted
How to show mathematically the equivalency between Ising Model and QUBO?
The relation between "Ising" and binary variables is following
$$
x_i = \frac{1 + s_i}{2},
$$
where $s_i$ is a spin and $x_i$ is a binary variable. Clearly setting $s_i = -1$ leads to $x_i = ...
- 14.9k
6
votes
Accepted
What does the notation $U(B,\beta) = \prod_{j =1}^n e^{-i \beta \sigma_j^x} $ mean in the context of QAOA?
I think there are two ways that you could denote the same thing. The first is what is done here:
$$
\prod_{j =1}^n e^{-i \beta \sigma_j^x}
$$
The second is
$$
\bigotimes_{j-1}^ne^{-i \beta \sigma^x},
$...
- 61.7k
6
votes
Accepted
QAOA for MaxCut - Algorithm motivation
What motivated this construction is mentioned in the original paper (section VI): adiabatic quantum computing. This construction is basically a Trotterized version of the evolution by the time ...
- 4,774
6
votes
Accepted
Is there a mistake in the VQE Ansatz in Cirq's tutorial?
You're right in the sense that the cost unitary, which is composed of all the $Z$ and $CZ$ gates does not affect the underlying probabilities of measuring a specific state by itself, however when we ...
- 990
6
votes
Accepted
Papers on classical optimization in QAOA
These papers might help:
Classical Optimizers for Noisy Intermediate-Scale Quantum Devices
Collective optimization for variational quantum eigensolvers
Also look at these optimizers from Pennylane.
- 14.1k
6
votes
Accepted
Do VQE and QAOA use the same Hamiltonian?
2-local forms
As I have seen the term, 2-local Hamiltonians are those Hamiltonians $\hat H$ which can be written as a sum of independent qubit operators $\hat H = \sum_i \sum_j \hat O_{ij}$, where ...
- 1,251
6
votes
Does QAO Ansatz have any better performance guarantees than QAOA?
The statement that "as $p \rightarrow \infty$, the minimum of the objective function is reached" is not correct. In fact, it is a pretty meaningless statement.
Commonly, a QAOA circuit has $...
- 3,284
6
votes
Accepted
Are there techniques to reduce the number of Pauli strings in a Hamiltonian?
Since Pauli strings form an (orthonormal) basis, and thus are linearly independent, the best approximation by other Pauli strings is to cut the Pauli strings with the smallest weight.
(Linear ...
- 7,853
5
votes
Accepted
In QAOA, why do we pick the initial Hamiltonian $B$ to be $\sigma_x$ applied to each qubit?
We don't really need $B = \sum \sigma_j^x$ in our QAOA algorithm. As long as you pick it in such a way that it doesn't commute with $C$. One of the reason is if they are commute, then they share a ...
- 14.1k
5
votes
Qiskit: Taking a QUBO matrix into `qubit_op'
There is actually a nice way in Qiskit to transform a matrix of an optimization problem into an qubit operator that can be translated into a quadratic program. I'll put here the example, note this is ...
- 2,685
5
votes
Accepted
Choosing a different optimizer when running QAOA in qiskit
The optimizers in Qiskit need to be instantiated then you can call their minimize() method. ...
- 1,583
5
votes
Accepted
TranspilerError: 'Number of qubits (40) in QAOA is greater than maximum (30) in the coupling_map'
The error is because the number of qubits in the hardware you are selecting, is less than what your QAOA circuit has (in this case 40). All you have to do is change the backend importing code, and ...
5
votes
Accepted
Optimization in QAOA should only return global minimum?
Since QAOA is an approximation method I would assume it is impossible to find the global minimum each time but others seem to disagree...
There's a difference between
being guaranteed to find the ...
- 7,969
4
votes
Accepted
Barren plateaus in quantum neural network training landscapes
First: The paper references [37] for Levy's Lemma, but you will find no mention of "Levy's Lemma" in [37]. You will find it called "Levy's Inequality", which is called Levy's Lemma in this, which is ...
4
votes
Accepted
How does the classical optimization of the angles $\gamma$ and $\beta$ in QAOA work?
$\langle \psi_p(\gamma,\beta)|H|\psi_p(\gamma,\beta)\rangle$ is basically the function evaluation step during the optimization. If you use a gradient-free optimizer, then it uses this information to ...
- 4,774
4
votes
Why do we transform a Boolean variable into a a Pauli Z matrix
The main thing that you're trying to do is create Hamiltonians whose ground states have a correspondence to basis vectors $|x\rangle$. So, the point of an operator
$$
R=\frac12(1-Z)=\left(\begin{array}...
- 61.7k
4
votes
Accepted
Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?
If you use infinite depth then QAOA can be consider as quantum annealer on gate-based. The authors of QAOA original paper probably deduce it from quantum annealing. What I mean by infinite depth is ...
- 14.1k
4
votes
Why QAOA with $p \rightarrow \infty $ gives the optimal solution?
The Quantum Approximate Optimization Algorithm is closely related to the Quantum Adiabatic Algorithm. Let's say we have a simple Hamiltonian (in our case $H_B$) with a known ground state and another ...
- 131
4
votes
Accepted
How to use Initial States in Qiskits QAOA?
You need to add the number of qubits for the initial state, this worked for me :
...
- 2,685
4
votes
Accepted
Is $\gamma \in [0,2 \pi]$ or $\gamma \in [0,\pi]$ in $CU1(2\gamma)_{(i,j)} $?
$\gamma$ should still go from $[0, 2\pi]$, as $U1$ also has domain on $[0, 2\pi]$. See https://qiskit.org/documentation/stubs/qiskit.circuit.library.U1Gate.html. $U1$ is cyclic mod $2\pi$ so in ...
- 690
4
votes
Properties of QAOA
QAOA is used for NP-Hard problems because it is a heuristic algorithm. You rarely (or almost never) use heuristic algorithms for problems that are simple.
Ad 1.) I am not sure if there is a problem in ...
- 81
4
votes
Solving higher-order (unconstrained) binary optimization problems with QAOA without quadratization
Ok so this is pretty late, but let me still try to answer it as an author of [1] :)
When you want to implement QUBO, what you're actually doing is implementing the corresponding Ising model. The steps ...
- 81
Only top scored, non community-wiki answers of a minimum length are eligible