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
2k 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 ...
user avatar
12 votes
1 answer
617 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 ...
user avatar
  • 1,009
11 votes
1 answer
300 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 ...
user avatar
11 votes
1 answer
278 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 ...
user avatar
  • 744
10 votes
1 answer
274 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 ...
user avatar
  • 22.4k
10 votes
1 answer
564 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, ...
user avatar
  • 453
9 votes
1 answer
538 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. ...
user avatar
  • 715
8 votes
3 answers
606 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,...
user avatar
  • 22.4k
8 votes
1 answer
462 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 &...
user avatar
7 votes
2 answers
299 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 ...
user avatar
  • 101
7 votes
1 answer
1k 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 ...
user avatar
7 votes
1 answer
188 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 ...
user avatar
  • 2,097
7 votes
0 answers
49 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 ...
user avatar
7 votes
1 answer
87 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,...
user avatar
  • 71
7 votes
1 answer
796 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 ...
user avatar
  • 249
6 votes
1 answer
457 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 ...
user avatar
6 votes
1 answer
986 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. ...
user avatar
6 votes
1 answer
155 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-...
user avatar
  • 291
6 votes
0 answers
98 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 ...
user avatar
6 votes
0 answers
189 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 ...
user avatar
5 votes
2 answers
216 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 ...
user avatar
  • 195
5 votes
2 answers
128 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. $...
user avatar
  • 153
5 votes
1 answer
80 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 ...
user avatar
  • 1,009
5 votes
2 answers
268 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 ...
user avatar
5 votes
1 answer
307 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. ...
user avatar
  • 81
5 votes
1 answer
69 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 ...
user avatar
  • 75
5 votes
0 answers
78 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 ...
user avatar
5 votes
0 answers
62 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 ...
user avatar
5 votes
0 answers
76 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 ...
user avatar
5 votes
0 answers
97 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 ...
user avatar
4 votes
1 answer
139 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 ...
user avatar
  • 2,097
4 votes
3 answers
335 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 ...
user avatar
4 votes
1 answer
78 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 ...
user avatar
  • 748
4 votes
2 answers
516 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 ...
user avatar
  • 85
4 votes
1 answer
281 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}...
user avatar
4 votes
1 answer
314 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 ...
user avatar
4 votes
2 answers
83 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,...
user avatar
4 votes
1 answer
375 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 ...
user avatar
  • 41
4 votes
0 answers
98 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}}(...
user avatar
  • 2,097
4 votes
0 answers
195 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{...
user avatar
4 votes
0 answers
314 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 &...
user avatar
  • 247
3 votes
2 answers
353 views

Does the Qiskit ADMM optimizer really run on quantum computers?

I read Qiskit quantum admm on this website. I doubt whether this Qiskit ADMM algorithm can run on a quantum computer. The code did import packages from Qiskit, but it doesn't create any quantum ...
user avatar
3 votes
1 answer
267 views

QAOA for MaxCut - Algorithm motivation

In the QAOA algorithm for MaxCut, the authors construct a very specific scheme where the qubits (corresponding to the vertices of the graph) are transformed using a sequence of unitaries $$|\gamma, \...
user avatar
  • 2,097
3 votes
2 answers
255 views

What exactly happening in QAOA in a general way?

So I know that in QAOA we have the two hamiltonians. Mixer and Cost Hamiltonian. Lets start: First we have our Qubits which get in the Superposition if we add the Hadamard Gate. Then we have the both ...
user avatar
  • 141
3 votes
2 answers
122 views

Question on practical quantum computing programming code [duplicate]

Has anyone tried any quantum computing programming code that shows or demonstrates the advantage of a quantum computer over classical computers? Thanks a lot.
user avatar
3 votes
1 answer
2k 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 ...
user avatar
3 votes
3 answers
574 views

How to run algorithms on IBMQ via Qiskit-Aqua?

I am trying to run an optimization problem on IBMQ. Running the same code on QASM simulator works fine. However, changing only the backend name to IBMQX takes long time. I am aware of the queues ...
user avatar
3 votes
1 answer
329 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 ...
user avatar
  • 438
3 votes
1 answer
245 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: ...
user avatar
  • 499
3 votes
1 answer
50 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....
user avatar