Hot answers tagged

19 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 ...
Marsl's user avatar
  • 899
12 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 \...
Gianni Mossi's user avatar
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 ...
jecado's user avatar
  • 1,106
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 "...
user1271772's user avatar
  • 13.5k
8 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 ...
user1271772's user avatar
  • 13.5k
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$ ...
Andrew O's user avatar
  • 1,729
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 ...
Faiyaz Hasan's user avatar
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 = ...
Martin Vesely's user avatar
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}, $...
DaftWullie's user avatar
  • 57.1k
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 ...
cnada's user avatar
  • 4,704
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 ...
Jack Ceroni's user avatar
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.
KAJ226's user avatar
  • 13.8k
6 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 ...
Cryoris's user avatar
  • 2,893
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 $...
MonteNero's user avatar
  • 2,369
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 ...
KAJ226's user avatar
  • 13.8k
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 ...
Lena's user avatar
  • 2,572
5 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 ...
jecado's user avatar
  • 1,106
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. ...
Steve Wood's user avatar
  • 1,343
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 ...
user1271772's user avatar
  • 13.5k
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 ...
cnada's user avatar
  • 4,704
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 ...
KAJ226's user avatar
  • 13.8k
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 ...
GiannisKol's user avatar
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 : ...
Lena's user avatar
  • 2,572
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 ...
Cuhrazatee's user avatar
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 ...
Adam Glos's user avatar
4 votes

How to solve quadratic programming problems with continuous variables and continous constraints by using quantum algorithms?

QUBO to QAOA/ADMM To solve a continuous variable problem like yours, you should use the ADMM optimizer, and here is how you should do it. 1. Keep your code in making the classical ...
Yet another Random Guy's user avatar
3 votes

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

If you decomposed your Hamiltonian into Pauli strings, and it has 100 different terms, then yes you can use one machine to do the quantum subroutine to evaluate the expectation for each of the term. $$...
KAJ226's user avatar
  • 13.8k
3 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}...
DaftWullie's user avatar
  • 57.1k
3 votes

QAOA Belongs into VQE or the other way around?

QAOA belongs to VQE. Indeed, the idea of VQE is to use a parametrized quantum circuit $U(\theta)$ to minimize $$\langle 0|U(\theta)^{\dagger}H_PU(\theta)|0\rangle$$ in order to obtain an ...
Arthur Pesah's user avatar
3 votes
Accepted

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

$C$ is a diagonal matrix, and $\max{C}$ is simply the maximum element (which is also the maximum eigenvalue, since the matrix is already diagonal). This is also what is usually meant by "maximum" ...
user1271772's user avatar
  • 13.5k

Only top scored, non community-wiki answers of a minimum length are eligible