Questions tagged [optimization]
For questions concerning how to improve quantum computers on different aspects like performance, efficiency or fault-tolerance.
166
questions
13
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
877
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,019
11
votes
4
answers
874
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,...
- 30.2k
11
votes
1
answer
332
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
314
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 ...
- 744
10
votes
1
answer
818
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.
...
- 687
10
votes
1
answer
175
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,312
10
votes
1
answer
321
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 ...
- 30.2k
10
votes
1
answer
628
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.1k
8
votes
1
answer
2k
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. ...
- 981
8
votes
1
answer
847
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
514
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 &...
- 16.9k
8
votes
1
answer
1k
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
415
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
1
answer
203
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,367
7
votes
1
answer
142
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
265
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
298
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
109
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 ...
- 377
6
votes
0
answers
241
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.1k
5
votes
2
answers
171
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,182
5
votes
2
answers
339
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,182
5
votes
2
answers
3k
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.1k
5
votes
2
answers
155
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. $...
- 435
5
votes
1
answer
91
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,019
5
votes
2
answers
284
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
437
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.1k
5
votes
1
answer
738
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
352
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
172
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 ...
- 341
5
votes
0
answers
56
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
0
answers
102
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
89
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.1k
5
votes
0
answers
109
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
99
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
3
answers
496
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 ...
- 137
4
votes
1
answer
144
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,367
4
votes
1
answer
144
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....
- 137
4
votes
1
answer
937
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 ...
- 448
4
votes
1
answer
366
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
104
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 ...
- 828
4
votes
2
answers
930
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 ...
- 95
4
votes
1
answer
333
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 ...
- 983
4
votes
2
answers
93
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
67
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
71
views
Numerical optimization over separable measurements
For a set of bipartite density operators $\{\rho_a\}_{a=1}^m \subset D(\mathcal{X} \otimes \mathcal{Y})$ each associated with a probability $p(a)$, an optimal separable measurement is a POVM $\{ \...
- 5,715
4
votes
0
answers
99
views
Forbidden/allowed outputs of a quantum channel
The coherent information of a channel $\mathcal{E}_{A'\rightarrow B}$ is defined as the maximum value obtained by the following function where the maximization is over all input states
$$I_{\rm{coh}}(...
- 2,367
4
votes
0
answers
236
views
General mixed integer linear programming problem with quantum computers
I was wondering if anyone had a sample code for running a general MILP problem. I saw some coding for some very specific problems and I thought they were kind of far away from what we needed.
$$
\text{...
4
votes
0
answers
447
views
Genetic algorithm does not converge to exact solution
I'm trying to evolve quantum circuits using genetic algorithms as they did in this paper Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians (Daskin &...
- 247