As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [optimization]

For questions concerning how to improve quantum computers on different aspects like performance, efficiency or fault-tolerance.

Filter by
Sorted by
Tagged with
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 ...
hopefully coherent's user avatar
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 ...
brzepkowski's user avatar
  • 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,...
Craig Gidney's user avatar
  • 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 ...
Daniel Yaacov's user avatar
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 ...
fr_andres's user avatar
  • 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. ...
incud's user avatar
  • 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 ...
Rajiv Krishnakumar's user avatar
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 ...
Craig Gidney's user avatar
  • 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, ...
asdf's user avatar
  • 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 ...
Martin Vesely's user avatar
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. ...
John Parker's user avatar
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 ...
Generic_dp's user avatar
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 &...
Sanchayan Dutta's user avatar
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 ...
karolyzz's user avatar
  • 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 ...
Minh Pham's user avatar
  • 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 ...
user1936752's user avatar
  • 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,...
soara's user avatar
  • 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-...
John Wong's user avatar
  • 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 ...
Natchapol Patamawisut's user avatar
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 ...
More Anonymous's user avatar
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 ...
Martin Vesely's user avatar
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} + ...
MonteNero's user avatar
  • 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 ...
MonteNero's user avatar
  • 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 ...
Martin Vesely's user avatar
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. $...
Jon Megan's user avatar
  • 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 ...
brzepkowski's user avatar
  • 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 ...
Pedro Pepê's user avatar
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}...
Martin Vesely's user avatar
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 ...
kontojulii's user avatar
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. ...
Lana's user avatar
  • 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 ...
consthatza's user avatar
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 ...
Soumik Adhikary's user avatar
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} ...
Chaithanya's user avatar
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 ...
Martin Vesely's user avatar
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 ...
César Leonardo Clemente López's user avatar
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 ...
Math.StackExchange's user avatar
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 ...
Gopal Dahale's user avatar
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 ...
user1936752's user avatar
  • 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....
Gopal Dahale's user avatar
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 ...
26118in's user avatar
  • 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: ...
Hannah's user avatar
  • 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 ...
C-Roux's user avatar
  • 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 ...
creet's user avatar
  • 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 ...
Enrique Segura's user avatar
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,...
Kenenbek Arzymatov's user avatar
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?
김재희's user avatar
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 $\{ \...
forky40's user avatar
  • 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}}(...
user1936752's user avatar
  • 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{...
Scientia Systems's user avatar
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 &...
Fernando's user avatar
  • 247