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