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
11
votes
1answer
207 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 ...
11
votes
1answer
209 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 ...
9
votes
1answer
227 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 ...
9
votes
1answer
395 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, ...
8
votes
1answer
136 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 ...
8
votes
1answer
1k 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 ...
8
votes
1answer
327 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 &...
7
votes
2answers
339 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,...
5
votes
2answers
227 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 ...
5
votes
1answer
63 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 ...
5
votes
0answers
86 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
1answer
62 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 ...
4
votes
1answer
221 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 ...
4
votes
1answer
50 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. ...
4
votes
1answer
314 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 ...
4
votes
0answers
40 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 ...
3
votes
1answer
105 views

Optimizing over 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 ...
3
votes
3answers
477 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 ...
3
votes
1answer
65 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 ...
3
votes
1answer
76 views

How does the fact that the output of a quantum circuit cannot be efficiently simulated classically help for optimisation?

This question refers principally to the article where for a low-depth circuit QAOA, the output cannot be efficiently simulated classically. I am wondering how this kind of quantum supremacy matters ...
3
votes
0answers
74 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. If ...
3
votes
0answers
165 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 &...
2
votes
1answer
85 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, \...
2
votes
1answer
155 views

Evolving a quantum circuit using a genetic algorithm

I've written a small quantum circuit simulator in python, so now I'm trying to evolve some circuits via genetic algorithms. My encoding is very simple, it's just a rectangular table of strings ...
2
votes
1answer
46 views

Quantum Annealing - Job Shop Problem

using this paper, I want to implement a solution for the Job Shop Problem on a D-Wave machine. One of the constraints mentioned in the paper, is $$ h_3(\bar{x}) = \sum_i \left(\sum_t x_{i,t}-1 \right)^...
2
votes
1answer
78 views

Optimise implementation of a quantum algorithm when an input is fixed

I need to implement a quantum comparator that, given a quantum register $a$ and a real number $b$ known at generation time (i.e. when the quantum circuit is generated), set a qubit $r$ to the boolean ...
2
votes
0answers
42 views

How can I implement partial transpose on a variable in Picos (Python, trying to solve an SDP)?

I try to optimise a quantity via an SDP. I optimise over all PPT measurement operators and hence have the constraints $\Pi_k^{T_B} \succeq 0$ (PPT) for my measurement operators. The part of the code ...
2
votes
0answers
88 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
votes
0answers
33 views

Quantum Optimization algorithms

The Harrow-Hassidim-Lloyd (HHL) algorithm for quantum matrix inversion (linear algebra) bridges classical math to quantum math and has been adopted for quantumizing many classical applications, such ...
2
votes
0answers
73 views

Quantum algorithms, combinatorial optimization, and approximation bounds

Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches. In particular, they ...
2
votes
0answers
43 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,...
2
votes
0answers
85 views

Optimal sampling strategy for VQE

In VQE we wish to minimize some cost function $F(\vec{x})$ that is dependent on a quantum state $\left| \psi_\vec{x} \right>$ which is prepared by a unitary $U(\vec{x})$ depending on some (...
1
vote
1answer
137 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 ...
1
vote
2answers
110 views

What is the risk factor on IBM's portfolio optimization notebook?

In the notebook "portfolio optimization" on IBM's platform the goal is to calculate the optimal stock selection using a classical and a quantum algorithm (VQE). A random portfolio is generated and ...
1
vote
1answer
42 views

SPSA max_trials

I'm using SPSA as an optimizer in VQE algorithm. The code runs on ibmq-qasm-simulator. I've set SPSA max_trials parameter to 500, but, when I run the code, it makes ...
1
vote
1answer
117 views

Applying Group Leaders Optimization to Quantum Belief Systems

Context: I am particularly interested in quantum cognition & would like to use a tool like pyZX to perform the following types of optimizations. In Preparing a (quantum) belief system they "...
1
vote
2answers
24 views

Layout Method in qiskit

Using transpile with optimization_level = 3, which is the layout method used by default?
1
vote
0answers
37 views

van Dam's proof for adiabatic optimization and graph diameter

My question concerns a proof in https://people.eecs.berkeley.edu/~vazirani/pubs/qao.pdf, "Limits on Quantum Adiabatic Optimization - Warning: Rough Manuscript!" by Wim van Dam and Umesh Vazirani. It ...
1
vote
0answers
26 views

Is there a limit to the size of problems that your simulators can run on Qiskit Aqua?

I'm trying to solve QUBO problems using Qiskit QAOA and VQE solvers. However, I have the experience that I can only solve small problems. I tried with both QAOA and VQE and both experience the same ...
1
vote
0answers
23 views

Entanglement and teleportation in quantum annealing and parallel computation

In classical optimization problems, some objective function's surface serves as a landscape for finding its minimum through minimization algorithms. Instead of your typical U-shaped objective ...
0
votes
2answers
32 views

How to stop optimization of a circuit during transpiling in web-interface of IBM Q?

I was playing with approximation of gates with Clifford+T group on IBM Q. Everything works well on simulator, however, when I tried to run my circuit on actual quantum processor, a transpiler ...
0
votes
1answer
64 views

Quantum algorithm for binary assignment problem

Based on the properties of the qubit, how could I solve this problem: I have 3 person A B C and 2 taxis T1 and T2 A and B are friends B and C hate each other A and C hate each other How could I ...
0
votes
1answer
57 views

What is Ising Hamiltonian ? What its role in Portfolio Diversification?

I am asking this question with reference to this https://github.com/Qiskit/qiskit-iqx-tutorials/blob/master/qiskit/advanced/aqua/finance/optimization/portfolio_diversification.ipynb Happy to know new ...
0
votes
0answers
38 views

Code for a simple optimization problem in Criq

For a demonstration, I would like to code a simple optimization problem in Cirq. I don't care what the problem is, but I want it understandable to someone who has had only basic algebra. One idea is ...