Quantum Computing Stack Exchange
Quantum Computing Stack Exchange

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).

193 questions
18
votes
1 answer

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 are its defining features that distinguish it…
Malcolm Regan
  • 773
  • 5
  • 11
16
votes
1 answer

What is the difference between QAOA and Quantum Annealing?

Edward Farhi's paper on the Quantum Approximate Optimization Algorithm introduces a way for gate model quantum computers to solve combinatorial optimization algorithms. However, D-Wave style quantum annealers have focused on combinatorial…
hopefully coherent
  • 727
  • 6
  • 15
14
votes
1 answer

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 papers and review articles (such as this one…
Nikita Nemkov
  • 1,725
  • 6
  • 22
12
votes
1 answer

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 variational quantum algorithms is NP-Hard. Does it mean we cannot…
Chao-Hua Yu
  • 303
  • 1
  • 6
11
votes
1 answer

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. Doesn't it cause the state to flip after evaluating…
John Parker
  • 1,181
  • 6
  • 15
10
votes
1 answer

Barren plateaus in quantum neural network training landscapes

Here the authors argue that the efforts of creating a scalable quantum neural network using a set of parameterized gates are deemed to fail for a large number of qubits. This is due to the fact that, due to the Levy's Lemma, the gradient of a…
asdf
  • 503
  • 3
  • 15
10
votes
1 answer

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 being diagonal in computational basis and the…
karolyzz
  • 299
  • 1
  • 7
9
votes
2 answers

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 then it will achieve Quantum Supremacy in an…
Nepomuk Hirsch
  • 495
  • 2
  • 5
8
votes
1 answer

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 layers simply act on the phases and therefore seem…
dncolomer
  • 148
  • 6
7
votes
2 answers

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 studies indicating that in some cases quantum annealing…
Martin Vesely
  • 15,244
  • 4
  • 32
  • 75
6
votes
0 answers

How to use Warm-Start QAOA in QisKit to solve non-convex QUBO problem?

I have a non-convex QUBO problem that I'd like to solve by warm-starting QAOA with a solution obtained from a continuous relaxation solution obtained by a classical algorithm. The specifics of the problem is shown below in the code. I have 2…
underdog987
  • 123
  • 6
6
votes
1 answer

Does the Lie closure of a set of Hamiltonians describe all unitaries you can generate with them?

Suppose we have $k$ Hermitian matrices $H_1, ..., H_k \in M_d(\mathbb{C})$. Define $\mathfrak{g} = \langle iH_1, ... iH_k \rangle_{\text{Lie}}$ to be the Lie algebra generated by these Hermitian matrices (i.e. the vector space spanned by these…
Alexey Uvarov
  • 716
  • 5
  • 15
6
votes
1 answer

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
26118in
  • 508
  • 5
  • 15
6
votes
1 answer

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 understand that quadratization from HOBO/HUBO to…
kontojulii
  • 61
  • 3
6
votes
1 answer

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 layer is a gate representation of the cost and…
Nepomuk Hirsch
  • 495
  • 2
  • 5
1
2 3
…
12 13