Questions tagged [optimization]
For questions concerning how to improve quantum computers on different aspects like performance, efficiency or fault-tolerance.
166
questions
2
votes
1
answer
211
views
Vertex Cover mappings from QUBO to Ising and vice versa
According to paper Ising formulations of many NP problems, Vertex Cover problem has the following Ising formulation:
$$\underset{x}{\text{min }} f(x) = a\sum_{(i,j) \in E}(1-x_i)(1-x_j) + b\sum_{i \in ...
- 1,300
5
votes
1
answer
734
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
3
votes
2
answers
164
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.
- 31
10
votes
1
answer
814
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
3
votes
0
answers
187
views
Implemented QAOA returns wrong result
I try to apply QAOA algorithm to find minimal energy state of the Hamiltonian:
$H_A = \frac{1}{2}\sigma_z^1 + \frac{1}{2}\sigma_z^1\sigma_z^2$
It is expected that with p=2 my variational should ...
- 53
6
votes
1
answer
263
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
3
votes
1
answer
374
views
Can QAOA solve a constraint optimization problem?
Can QAOA solve a constraint binary optimization problem? QAOA is short for Quantum Approximate Optimization Algorithm. I read the information https://qiskit.org/textbook/ch-applications/qaoa.html.
But ...
- 61
3
votes
2
answers
413
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 ...
- 61
3
votes
1
answer
130
views
To find the best angles in QAOA why we do not optimize over a maximum ofall shots instead of a mean?
When finding the best angles for QAOA we optimize over $F_{p}(\beta , \gamma) = \langle \psi_p(\gamma,\beta)|C|\psi_p(\gamma,\beta)\rangle $.
In each optimization step we simulate the circuit $m$ ...
- 519
0
votes
1
answer
228
views
Is there a quantum circuit to find the maximum of two inputs?
Is there a quantum circuit (preferably on Quirk as an example) that will enable me to find the maximum from two inputs?
Example
input A: 11011
input B: 11100
Expected output: 11100
- 23
2
votes
0
answers
137
views
How to implement the Maximum or Minimum Searching Algorithm (QUMMSA) circuit in Quirk?
I am Java and Python programmer who started self-learning Quantum Computing a couple of months back. The journey has been thus far very tough. I have been using QisKit and Quirk to learn by in ...
- 23
2
votes
1
answer
286
views
How to solve QUBO problems in Q#?
Short version:
I'm trying to solve a traveling salesman problem very similar to the traveling Santa example here: http://quantumalgorithmzoo.org/traveling_santa/, which is also included in the samples ...
- 21
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
5
votes
1
answer
434
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
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
1
vote
1
answer
128
views
Qiskit: Error when importing libraries for ADMM optimizer
I would like to try and ADMM optimizer as shown in Qiskit Tutorial in Quantum Lab. Firstly, I imported necessary libraries (copy/paste from the Tutorial):
...
- 13.1k
2
votes
1
answer
323
views
Quadratic optimization in Qiskit: Error when QuadraticProgram with quadratic constraint converted to QUBO
I prepared a quadratic optimization task with binary and integer variables and linear and quadratic constraints. I fed it into QuadraticProgram in Qiskit. After ...
- 13.1k
2
votes
1
answer
144
views
Quantum Circuit Optimization with Machine Learning [closed]
I read some paper about Quantum Circuit Optimization but I am on a low level.
And have some experience in ML.
But what I don't understand is it possible that ML can help to optimize Quantum Circuits ...
- 141
-1
votes
1
answer
157
views
Implementing a circuit that returns $|01\rangle$ and $|10\rangle$ with equal probability
Using Python how can I implement a quantum circuit that returns $|01\rangle$ or $|10\rangle$ using only $CX$, $RX$ and $RY$ gates, starting with random parametric gates as parameters and optimizing it ...
2
votes
2
answers
282
views
Qiskit sample - Portfolio optimization
I've recently tried to run this sample from Qiskit (Portfolio Optimization)
I was able to change RandomDataProvider to YahooDataProvider and able to run it on real stock prices.
However, there is one ...
- 121
3
votes
0
answers
157
views
What is the query complexity of the QUBO algorithm?
What is the complexity of the quantum unconstrained binary optimization (QUBO) algorithm in the number of queries to the quantum processor?
To clarify, I'm asking about the complexity on quantum ...
- 131
2
votes
1
answer
139
views
Optimization using Quantum Logics
Is it possible to solve the following kind of optimization using Quantum Computing?
Minimize
5*x1 - 7*x2
binary
x1
x2
If yes, is it possible to have a sample code ...
- 183
2
votes
1
answer
140
views
How can I solve the problem of optimisation the quantum computer?
I am trying to solve the problem of optimization (VRP) with genetic algorithm and quantum computing in the platform IBM Q Experience.
But I am unable to advance on this. How can I do it?
According to ...
- 23
5
votes
1
answer
350
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
0
answers
108
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 ...
0
votes
2
answers
163
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 ...
- 13.1k
1
vote
2
answers
181
views
Layout Method in qiskit
Using transpile with optimization_level = 3, which is the layout method used by default?
- 13
1
vote
1
answer
171
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 ...
- 31
2
votes
0
answers
54
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 ...
- 311
1
vote
0
answers
47
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 ...
- 11
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
8
votes
1
answer
843
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
0
votes
2
answers
720
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 ...
- 167
1
vote
2
answers
255
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 ...
- 11
2
votes
0
answers
392
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 ...
- 121
2
votes
1
answer
95
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)^...
- 107
3
votes
1
answer
307
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,357
1
vote
1
answer
173
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 ...
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,357
4
votes
1
answer
143
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,357
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
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
1
vote
0
answers
37
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 ...
- 945
2
votes
0
answers
70
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 ...
- 945
3
votes
0
answers
103
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 ...
- 1,036
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{...
3
votes
1
answer
103
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 ...
- 4,624
4
votes
1
answer
332
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
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
12
votes
1
answer
875
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