# Tag Info

12

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 MaxCut). Let me explain The VQE - Variational Quantum Eigensolver - solves the problem of approximating the smallest eigenvalue of some Hermitian operator $H$ which ...

9

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 they are part of a growing body of literature arguing very wisely that the complexity of classical optimization cannot be ignored, when assessing the complexity of ...

8

"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 "quantum supremacy" would almost not exist at all. Even Shor's algorithm for factoring numbers in polynomial time would not be considered "superior" ...

6

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},$$ which I imagine is what you're thinking of. In the first expression, note the subscript on the Pauli matrix. This means that it's an operator over all $n$ ...

6

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 dependent hamiltonian: $$H(t) = (1-t/T)B + (t/T) C$$ where T is the total runtime. The Trotterized evolution consists of alternately applying $U_{C}$ and $U_{B}$. ...

6

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 apply the mixer (the layer of $Rx$ gates), the probabilities are changed, due to these added phases. Let's look at a basic example, to convince you that ...

6

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.

6

"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 algorithm where we can prove that a search that would cost $\mathcal{O}(N)$ on a classical computer can be done with only $\mathcal{O}(\sqrt{N})$ on a quantum ...

5

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 common eigenvector. Then if you run into this type of situation, you will never get out, and you will be stuck in this state. You can think of $U(\beta, B)$ as a ...

5

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 possible for many optimization problems, find every one here in case you want to test something else! For example here it is done for MaxCut and TSP, it could ...

5

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 operators. The website you provided talks about the Hamiltonian in terms of the Pauli X and Z matrices; $\hat\sigma^x$ and $\hat\sigma^z$. If you want to compute ...

5

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 each $\hat O_{ij}$ acts non-trivially only on two qubits $i$ and $j$. This is as opposed to a global Hamiltonian, whose terms may act on any number of qubits. This ...

4

$\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 drive its search. Depending on the optimizer if it needs them to update the parameters. You seem confused between the simulation and measurement part. $\langle ... 4 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 not cited in the paper you mention. Second: There is an easy proof that this claim is false for VQE. In quantum chemistry we optimize the parameters of a ... 4 You need to add the number of qubits for the initial state, this worked for me : n_qubits = 2 #or whatever you want for your example qaoa_mes = QAOA(H, p=p, optimizer=optimizer, initial_state = Zero(n_qubits), quantum_instance=Aer.get_backend("qasm_simulator")) You can also pass a list for the initial point, for example : qaoa_mes = QAOA(H, p=p, ... 4$\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 general one cannot distinguish$U1(x \pm 2\pi)$4 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 which QAOA is clearly better than its classical counterparts. However, it was "proved" that it is hard to simulate even a single layer of QAOA [1]. ... 3$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" and "minimum" in this "quantum optimization" literature, which includes adiabatic quantum computing (AQC), quantum annealing, and QAOA. 3 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. $$\langle H \rangle = \sum_{i} h_i \langle P_i \rangle$$ So you can evaluate$\langle P_1 \rangle$on one machine and$\langle P_2 \rangle$on another machine..... 3 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 you take$p \to \infty$in the operator $$U(\beta, \gamma) = \Pi_{i=1}^p U_B(\beta_i)U_C(\gamma_i)$$ Your are right about the commutation problem. However, ... 3 There are a few ways to speed up this execution in Aqua. One way in the case of noiseless simulation is to use SLSQP instead of Cobyla, which we've noticed empirically seems to converge faster in noiseless environments. Another is to set skip_qobj_validation=True in the QuantumInstance init. I would start with these two and see how they do. QAOA in general ... 3 There is a parameter when instantiating a QuantumInstance() called skip_qobj_validation. This parameter is set to True by default. When creating the QuantumInstance, you can set it to False, and that will get rid of the warning. q_instance = QuantumInstace(skip_qobj_validation=False) 3 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$which is impractical. In addition if$T$is too long you're likely to not find the solution as the probability is not monotonic. I believe an example of this can be ... 3 It can actually and this is done by adding penalties to include the constraints in the cost function. See this article on formulations of different problems. There also exist an adaptation for constrained problems. See this articla on the Quantum Alternating Operator Ansatz. 3 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 Hamiltonian$H_C$, whose ground state we want to calculate. Consider the time-dependent Hamiltonian H(t) = \left(1-\frac{t}{T}\right)H_B(t) + \... 3 I will give you a partial answer cocerning using quantum machine learning methods in NISQ era. As any other quantum algorithm, QML algorithms can be used on current NISQ processors. However, there is a problem with noise leading to quick decoherence of qubits. Especially entangled qubits (which are crucial for quantum computing) are very sussceptible to ... 3 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 adiabaticity by starting with the ground state$|+\rangle^{\otimes n}$of the (mixing) Hamiltonian$H_M = \sum_i \sigma_i^x$. Now, if we slowly change a ... 3 You can use a cirq.DensePauliString to represent a tensor product of Paulis: gate = cirq.DensePauliString("IIZZIZ") a, b, c, d, e, f = cirq.LineQubit.range(6) op1 = gate(a, b, c, d, e, f) It can be a bit tedious to specify all those identities, and to manage making sure you pass the right qubit into the right position, so I'd recommend directly ... 3 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 \rangle$and you want to use QAOA to find the ground state of some cost Hamiltonian$H_C$. I'm using the notation$\big\{\lvert x \rangle : x \in \{\pm 1\}^n \...

3

First of all, QAOA can be regarded as an application of VQE. (Take a look at this answer.) Therefore, we can consider their performance to be similar enough to talk about them together. Although for some particular cases, a quantum computer isn't even needed for QAOA, but let's consider only the cases in which quantum circuits are used. Briefly, it is not ...

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