Questions tagged [optimization]
For questions concerning how to improve quantum computers on different aspects like performance, efficiency or fault-tolerance.
180
questions
15
votes
1
answer
3k
views
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 ...
12
votes
1
answer
972
views
Is there a general method of expressing optimization problem as a Hamiltonian?
Let's say, that we have an optimization problem in the form:
$$ \min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,
$$
where $f(x)$ is an objective function, $g_i(x)$ are ...
- 1,029
11
votes
1
answer
944
views
Comparing method of differentiation in variational quantum circuit
Training of variational circuits needs to calculate the derivative to be optimized. Several methods were proposed (1), the most famous ones being the finite difference and the parameter shift rule.
...
- 671
11
votes
4
answers
944
views
Minimum number of CNOTs for Toffoli with non-adjacent controls
I want to decompose a Toffoli gate into CNOTs and arbitrary single-qubit gates. I want to minimize the number of CNOTs. I have a locality constraint: because the Toffoli is occurring in a linear array,...
- 33.3k
11
votes
1
answer
353
views
Devising "structured initial guesses" for random parametrized quantum circuits to avoid getting stuck in a flat plateau
The recent McClean et al. paper Barren plateaus in quantum neural network training landscapes shows that for a wide class of reasonable parameterized quantum circuits, the probability that the ...
- 213
11
votes
1
answer
338
views
Is there any general statement about what kinds of problems can be approximated more efficiently using a quantum computer?
As the name already suggests, this question is a follow-up of this other. I was delighted with the quality of the answers, but I felt it would be immensely interesting if insights regarding ...
- 754
10
votes
1
answer
263
views
Categories and types of quantum inspired algorithms
I have a question concerning "quantum-inspired" algorithms. There seem to be several types of algorithms that fall into this category. Some examples are:
Ewin's dequantized algorithms
...
- 1,644
10
votes
1
answer
364
views
Minimum number of CNOTs for a 4-qubit increment on a planar grid
Recently I've been wondering how high NISQ machines will be able to "count". What I mean by that is, given the most optimized increment circuit you can make, how many times can you physically apply ...
- 33.3k
10
votes
1
answer
657
views
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, ...
- 493
10
votes
1
answer
2k
views
Travelling salesman problem on quantum computer
Recently a pre-print of article Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience appeared. The authors use a phase estimation as a core for their ...
- 13.6k
8
votes
1
answer
3k
views
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. ...
- 1,031
8
votes
1
answer
1k
views
What are the differences between the different transpiler optimization levels in qiskit
I am currently running a simple algorithm using Qiskit and I am running it for various transpiler optimization levels (0-3). I wish to know what exactly occurs differently when for example I run the ...
- 128
8
votes
1
answer
552
views
Understanding the Group Leaders Optimization Algorithm
Context:
I have been trying to understand the genetic algorithm discussed in the paper Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians (Daskin &...
- 17.2k
8
votes
1
answer
2k
views
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 ...
- 269
7
votes
2
answers
467
views
Complexity of $n$-Toffoli with phase difference
I'm interested in the $n$-Toffoli gates with phase differences. I found a quadratic technique in section 7.2 of this paper.
Here's the front page of the paper.
Here's an image of the section that I'm ...
- 101
7
votes
2
answers
161
views
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 ...
- 13.6k
7
votes
1
answer
215
views
Closest quantum state with a fixed marginal: Analytical solution?
Let $\rho_{AB}$ be a bipartite state and let $\sigma_{B}$ be another state. What state $\tilde{\rho}_{AB}$ is closest to $\rho_{AB}$ and satisfies $\tilde{\rho}_B = \sigma_B$? We can define closeness ...
- 2,597
7
votes
1
answer
199
views
Enforcing a particular layout mapping in Qiskit
I would like to ask how to set a particular layout during transpiling. I guess that the layout can be set by the initial_layout parameter in the transpiler. However,...
- 71
6
votes
1
answer
1k
views
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<j}J_{ij}s_is_j,$$
and a Quadratic Unconstrained Binary Optimization (QUBO) problem with binary ...
- 478
6
votes
1
answer
353
views
Why QAOA with $p \rightarrow \infty $ gives the optimal solution?
In the QAOA paper, it is shown that the optimal value of the p-ansatz $M_p$ converges to $\max_z C(z)$ as $p \rightarrow \infty$ on page 10. The proof is to relate to QAOA by considering the time-...
- 291
6
votes
1
answer
397
views
How linear combination of unitaries gradient work (Qiskit, PennyLane)?
I'm trying to implement linear combination of unitaries(LCU) gradient from Qiskit Gradient Framework
but on PennyLane.
First, i looked through the source code in Qiskit.
In Qiskit LCU gradient if we ...
6
votes
0
answers
117
views
Is No Free Lunch Theorem generalizable to Quantum Computation?
The "No Free Lunch Theorem" says: that when averaged across all possible problems, any two strategies have equivalent performance. However it uses Bayesian reasoning to arrive at this ...
- 429
6
votes
0
answers
297
views
Solving linear system $Ax=b$ with exponential speed-up via binary optimization?
The main disadvantage of HHL algorithm for solving $A|x\rangle = |b\rangle$ is that exponential speed-up is reached only in case we are interested in value $\langle x|M|x\rangle$, where $M$ is a ...
- 13.6k
5
votes
2
answers
190
views
Under what conditions the minimum eigengap is non-zero?
I would like to know sufficient conditions for a non-zero eigengap of a time-dependent Hamiltonian.
Suppose we have a time-dependent Hamiltonian $H(t)$ defined as follows:
$$H(t) = (1-s(t))H_{init} + ...
- 2,359
5
votes
2
answers
414
views
Role of entanglement in a VQE ansatz for combinatorial problems
Variational Quantum Eigensolver is used in quantum chemistry and combinatorial optimization (CO). I'm interested in the latter. In the CO setting a Hamiltonian is a diagonal matrix with real entries ...
- 2,359
5
votes
2
answers
4k
views
How to convert QUBO problem to Ising Hamiltonian?
According to paper Ising formulations of many NP problems an unconstrained quadratic programming problem
$$
f(x_1, x_2,\dots, x_n) = \sum_{i}^N h_ix_i + \sum_{i < j} J_ix_ix_j
$$
can be expressed ...
- 13.6k
5
votes
2
answers
160
views
maximization of trace between two operators with respect to different norm constraints
I want to maximize $\text{Tr}(XY)$ over $X$ for fixed $Y$, where $X$ and $Y$ are both hermitian (but doesn't necessarily positive) operators, and $X$ is constrained by its p-norm bounded by $1$, i.e. $...
- 465
5
votes
1
answer
105
views
How to tell if the ground states of two Hamiltonians are solutions of the same optimization problem?
Let's say, that we have an optimization problem in the form:
$$ \min_x f(x) \\ g_i(x) \leq 0, i = 1, ..., m \\ h_j(x) = 0, j = 1, ..., p,
$$
where $f(x)$ is an objective function, $g_i(x)$ are ...
- 1,029
5
votes
2
answers
312
views
Resources on hybrid quantum-classical algorithms applied to combinatorial optimization problems
I am doing a thesis on "Metaheuristics and Quantum Computing", and was wondering if anyone could recommend some papers/pages
to read talking about hybrid quantum/classical computing.
(My idea is to ...
- 53
5
votes
1
answer
495
views
Can QAOA be considered as simulation of a quantum annealer on a gate-based quantum computer?
Quantum annealers are single purpose machines allowing to solve quadratic unconstrained binary optimization (QUBO) problems. QUBO problems have following objective function:
$$
F=-\sum_{i<j}J_{ij}...
- 13.6k
5
votes
1
answer
891
views
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 ...
- 51
5
votes
1
answer
375
views
Qiskit Portfolio Optimization Application
I recently got flung into the world of quantum computing and I'm a beginner at coding. I was assigned to do the Portfolio Optimization tutorial of the Qiskit Finance Tutorials and input real data. ...
- 81
5
votes
1
answer
92
views
Recent experimental demonstrations of variational quantum algorithms?
I am interested in the recent experimental demonstrations of variational quantum algorithms.
Can someone please provide me with a list of references of recent experimental demonstrations of ...
5
votes
1
answer
268
views
Qiskit: QAOAnsatz circuit with custom Hamiltonian
I am trying to implement the Quantum Approximate Optimization Ansatz by creating a parametrized subcircuit
$$V (α) = e^{−iH_M α_1} e^{−iH_D b_1} ... e^{−iH_M α_n} e^{−iH_D b_n}$$
with the custom ...
- 351
5
votes
0
answers
99
views
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 ...
- 111
5
votes
0
answers
106
views
Lowest energy problem with additional constraints
Consider the following minimization problem:
\begin{align}
&\min_{\rho} \mathrm{Tr}[\rho H] \\
\text{such that:}& \\
&Tr[\rho A_i] \leq 0 \ \ \forall A_i, \ i \in \{1,2,3,...\}
\end{align}
...
- 71
5
votes
0
answers
125
views
Computing the expectation values of a Hamiltonian constructed from a cost functions in combinatorial optimization
One of the main steps in Hybrid Quantum algorithms for solving Combinatorial Optimization problems is the calculation of the expected value of a hermitian operator $H = \sum{H_i}$ (where $H_i$ are ...
5
votes
0
answers
105
views
Application of classical approximate optimization algorithm to bottlenecks of quantum computing
According to J. Gough, one of the bottlenecks in the current development of large-scale quantum computing may be the lack of our ability to simulate large scale quantum system, which is a NP-hard ...
4
votes
2
answers
165
views
Does the gradient commute with the partial trace?
Suppose I have a parameterized quantum state: $\rho(\theta) = U(\theta) \rho U^\dagger(\theta)$. I am curious to know whether the following holds:
$\frac{\partial \text{Tr}_A (\rho(\theta))}{\partial \...
- 465
4
votes
3
answers
561
views
Cost of SWAP gate
We know that a SWAP gate needs three CNOT gates but I have seen papers which say that a SWAP gate can be achieved by necessary rewiring can are not counted towards the final quantum cost. I am ...
- 147
4
votes
1
answer
150
views
How to maximise over linear functionals of quantum channels?
I am given fixed quantum states $\rho_X$ and $\sigma_Y$ and some function of the form $\text{Tr}(N_{X\rightarrow Y}(\rho_X)\sigma_Y)$. I would like to maximize this function over all completely ...
- 2,597
4
votes
1
answer
220
views
T-depth in Qiskit
How to find T-depth in Qiskit? Is there any inbuilt function or some method to find T-depth? I know that the .depth() function exists which returns circuit depth (i....
- 147
4
votes
1
answer
459
views
How does the classical optimization of the angles $\gamma$ and $\beta$ in QAOA work?
I have been trying to implement QAOA with classical optimization of the angles $\gamma$ and $\beta$, but I I'm failing at the classical part.
In paper Quantum Approximate Optimization Algorithm: ...
- 519
4
votes
1
answer
129
views
How to explain that I get a value lower than the smallest possible through minimization procedure in VQE?
As far as I know after minimization I have to obtain a value $E_{0}\le \frac{\langle \psi (\theta)|H|\psi (\theta)\rangle}{\langle \psi (\theta)|\psi (\theta)\rangle}$, where $E_{0}$ - eigenvalue of ...
- 848
4
votes
2
answers
1k
views
From QUBO matrix to Ising model in Qiskit
Given a general QUBO matrix $Q$ for a quadratic minimization problem, is there a Qiskit way to obtain the Pauli gate list or the Ising model for it? A related question is Qiskit: Taking a QUBO matrix ...
- 105
4
votes
1
answer
354
views
How to implement NM Algorithm for Variational Quantum Eigensolver?
First of all: thanks for reading again. I appreciate the feedback I have gotten from this community the past weeks as I started to feel ready to ask questions about quantum computing topics.
I am ...
- 993
4
votes
2
answers
103
views
What does it mean to have 2000 qubits and 6016 couplers?
From official D-Wave docs:
The D-Wave 2000Q QPU has up to 2048 qubits and 6016 couplers.
For example, I have the optimization problem defined as the QUBO problem.
If I want to solve it on D-Wave,...
4
votes
1
answer
93
views
Are there some review papers of quantum combinatorical optimization problem and their application?
I'd like to get recommendations for review paper summarized for combinatorical optimization algorithm and application. Are there any papers that have been organized recently?
- 41
4
votes
0
answers
94
views
Qiskit QAOA optimization does not work when setting simulation seed in AerSampler
I am using Qiskit's QAOA for optimization and I would like to extract the probabilities distribution obtained in the optimization loop when running the circuit with the optimal parameters set. To do ...
- 41
4
votes
0
answers
59
views
When is a quantum algorithm considered to have a significantly superior performance over another quantum algorithm?
Suppose we have two heuristic quantum algorithms $A$ and $B$ that attempt to solve a certain class of optimization problems. Let's suppose that the benchmarking metric is Time To Solution (TTS), which ...
- 2,359