13 votes
Accepted

Comparing method of differentiation in variational quantum circuit

Both finite differences and the parameter-shift rule can be used to compute quantum gradients on quantum hardware. However, there are several reasons that lead to the parameter-shift rule being ...
user avatar
9 votes
Accepted

Is there a general method of expressing optimization problem as a Hamiltonian?

As requested in the comments, here is a worked example. The main body deals with minimizing $f(x)$ for a specific problem. At the bottom follows a brief discussion of constraints then a brief ...
user avatar
  • 549
7 votes
Accepted

Optimizing over quantum channels

For the specific linear function you are interested in, the solution turns out to be trivial: you can take the channel to be $N_{X\rightarrow Y}(\rho) = \operatorname{Tr}(\rho) |\psi\rangle\langle \...
user avatar
  • 4,413
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 ...
user avatar
  • 4,554
6 votes
Accepted

What are the differences between the different transpiler optimization levels in qiskit

These levels are provided via "preset passmanagers" in Qiskit. These are simple-to-use transpiler pipelines, but you can also build your own passmanager pipeline. You can see what each does by ...
user avatar
  • 1,542
6 votes

Complexity of $n$-Toffoli with phase difference

(This answer uses ancillae and feedback) Does anyone know if there has been any improvement on the decomposition of the general n-qubits control X with phase differences in terms of elementary gates ...
user avatar
  • 21.8k
5 votes
Accepted

How to tell if the ground states of two Hamiltonians are solutions of the same optimization problem?

Short Answer: It is potentially hard (as bRost03 indicates in the comments). To be precise, coNP-hard. Longer Answer: In adiabatic quantum computation, the ground-...
user avatar
5 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$ ...
user avatar
  • 1,679
5 votes
Accepted

How to convert QUBO problem to Ising Hamiltonian?

Maybe this will help. Let's take a simple case: $$f(x_1, x_2) = -2x_1 x_2$$ Then it is minimum when $x_1 = x_2 = 1$. Now let's take this Hamiltonian: $$H_f = -2Z \otimes Z$$ The Hamiltonian is minimum ...
user avatar
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 ...
user avatar
  • 11.9k
4 votes
Accepted

Devising "structured initial guesses" for random parametrized quantum circuits to avoid getting stuck in a flat plateau

I am not an expert but I read a few papers and here is what I have found. Similarly to NN, people found strategies to avoid this issue with the gradients. Basically, for some problems, you can use ...
user avatar
  • 413
4 votes
Accepted

Minimum number of CNOTs for a 4-qubit increment on a planar grid

Here is the best circuit I've found. It uses 14 CNOTs. Note that this circuit is not using a linear layout! It is placed on the grid like this: ...
user avatar
  • 21.8k
4 votes
Accepted

Resources on hybrid quantum-classical algorithms applied to combinatorial optimization problems

So for hybrid quantum-classical algorithms, I suggest looking at : The Quantum Approximate Optimization Algorithm Variational hybrid quantum-classical algorithms that include the so famous ...
user avatar
  • 4,554
4 votes

How to explain that I get a value lower than the smallest possible through minimization procedure in VQE?

The proof of the variational theorem (the theorem that the ground state energy is the lowest possible energy you can get from $\frac{\langle \psi|H|\psi\rangle}{ \langle \psi | \psi \rangle}$) is ...
user avatar
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 ...
user avatar
  • 4,554
4 votes

Does the Qiskit ADMM optimizer really run on quantum computers?

The ADMM optimizer is a classical optimizer that will be execute on the classical computer. Nowadays, because of the limitation of the hardware, we see a lot of hybrid quantum-classical algorithms. In ...
user avatar
  • 12.3k
4 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 \...
user avatar
4 votes

Complexity of $n$-Toffoli with phase difference

Feedback is not allowed and no ancilla qubits are used. Here's a relative-phase-error no-ancilla $C^n X$ construction with a T count of $12n \pm O(1)$. I think it's easiest to understand as $3n \pm O(...
user avatar
  • 21.8k
4 votes

maximization of trace between two operators with respect to different norm constraints

If I understand your question correctly, you're trying to prove something that is false. Consider the operator $$ Y = \begin{pmatrix} 2 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 &...
user avatar
  • 4,413
3 votes
Accepted

How to implement NM Algorithm for Variational Quantum Eigensolver?

If you are looking for a more complete implementation of a quantum variational algorithm in the context of Cirq, I would recommend looking at the second example in the OpenFermion-Cirq notebook found ...
user avatar
3 votes
Accepted

Evolving a quantum circuit using a genetic algorithm

So in your example, you try to find the quantum circuit representing the Toffoli operation. I would then change my objective/fitness function and compare the unitary matrix representing the operation. ...
user avatar
  • 4,554
3 votes
Accepted

Minimum number of CNOTs for Toffoli with non-adjacent controls

Here is the best construction I've found. It uses 8 CNOTs. I verified this circuit in Quirk using the channel-state duality and a known-good inverse. The target is the middle qubit. None of the ...
user avatar
  • 21.8k
3 votes

Minimum number of CNOTs for Toffoli with non-adjacent controls

I believe I've got it down to 9 controlled-not gates: What I did was I used a set of three cNots in the place of Swap to move the two controls next to each other to achieve the last part of the ...
user avatar
  • 46.2k
3 votes
Accepted

Is there any general statement about what kinds of problems can be approximated more efficiently using a quantum computer?

The Quantum Approximate Optimization Algorithm is a good place to start for analyzing the relative performance of quantum algorithms on approximation problems. One result so far is that at p=1 QAOA ...
user avatar
3 votes

Qiskit Portfolio Optimization Application

I changed the stock parameter to a list of strings and added the line stockmarket = StockMarket.NASDAQ as such: ...
user avatar
  • 81
3 votes
Accepted

Optimization using Quantum Logics

Qiskit has an optimization module and you can find tutorials that illustrate its functionality here. To solve the example you posted, e.g., with the Quantum Approximate Optimization Algorithm (QAOA), ...
user avatar
3 votes
Accepted

Quadratic optimization in Qiskit: Error when QuadraticProgram with quadratic constraint converted to QUBO

Thank you for your report. I investigated the details and fixed the bug with this pull request.
user avatar
  • 46
3 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 ...
user avatar
  • 12.3k
3 votes

Can QAOA solve a constraint optimization problem?

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 ...
user avatar
  • 4,554
3 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 ...
user avatar

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