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 ...
- 744
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 ...
- 579
8
votes
Accepted
How to maximise over linear functionals of 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 \...
- 4,793
7
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 ...
- 1,582
7
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 \...
- 400
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,594
6
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,699
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 ...
- 27.6k
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-...
- 11.4k
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 ...
- 4,138
5
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 ...
- 370
5
votes
Accepted
T-depth in Qiskit
The depth method can be customized with a gate subset you want to consider. To compute the $T$-depth you most likely want to include both $T$ and $T^\dagger$ gates. ...
- 1,343
5
votes
Accepted
Under what conditions the minimum eigengap is non-zero?
I think this is formally undecidable.
In detail, Cubitt, Perez-Garcia, and Wolf (arxiv, Nature) reduced the problem of determining the gap of a translationally-invariant Hamiltonian to the problem of ...
- 8,476
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 ...
- 12.5k
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 ...
- 443
4
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 ...
- 27.6k
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 ...
- 4,594
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:
...
- 27.6k
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 ...
- 41
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,594
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 ...
- 13k
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(...
- 27.6k
4
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 = ...
- 12.7k
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 &...
- 4,793
4
votes
Accepted
Cost of SWAP gate
Swaps are never truly free. The papers you linked are just ignoring the cost of routing, and then hiding the cost of swapping in that ignorance.
We ignore all concerns of layout and communication ...
- 27.6k
4
votes
Categories and types of quantum inspired algorithms
My reply is by no means an answer to your question. However, I still would like to drop in my 2 cents.
The notion of "quantum-inspired" algorithms has no formal definition and has a rather ...
- 1,758
3
votes
Accepted
Travelling salesman problem on quantum computer
Based on comment by DaftWullie and my experience with the algortihm, it seems that a title of the article is misleading.
The authors claim that algorithm they proposed is efficient. However, this is ...
- 12.7k
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 ...
3
votes
Minimum number of CNOTs for Toffoli with non-adjacent controls
I found this circuit with T-depth 3 using CPFlow (shameless plug).
Non-clifford gates (with T-count 1) are $R_Z(\pi/4)$ and $R_X(\pi/4)$. While most of the single-qubit non-Clifford gates in this ...
- 1,343
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. ...
- 4,594
Only top scored, non community-wiki answers of a minimum length are eligible