Quantum Computing Stack Exchange
Quantum Computing Stack Exchange

Questions tagged [qubo]

Questions about or related to QUBO (quadratic unconstrained binary-function optimization).

36 questions
21
votes
2 answers

Did D-Wave show quantum advantage in 2023?

I would like to know your thoughts on whether or not D-Wave has shown a a smoking-gun example of quantum advantage this year. I am genuinely not quite sure what to think, but I believe the answer to this question is important in understanding the…
sheesymcdeezy
  • 2,021
  • 8
  • 27
9
votes
1 answer

Inequality constraints on D-Wave (using PyQUBO)

Inequalities cannot be directly converted into a QUBO form. By inequality, I mean something like this: 0⩽ Expression ⩽ N. We can introduce a slack variable and convert it to an equality problem: ⟹ Expression + s = N where: s ∈ Z, s ∈ [0,N] Since the…
amp
  • 91
  • 1
6
votes
0 answers

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 problem is shown below in the code. I have 2…
underdog987
  • 123
  • 6
6
votes
1 answer

Can D-Wave machines solve QUBO problems more efficiently than gate model devices?

I'm new to quantum annealing and D-Wave computer. I saw that it has about 5000 qubits which can solve a QUBO problem with 5000 variables. From my understanding, if we use a gate model device, say, an IBM quantum device to solve a QUBO problem, the…
peachnuts
  • 1,485
  • 1
  • 10
  • 15
5
votes
0 answers

How to calculate the $r^{\text{th}}$ digit of $\sum ^{j−1}_{p=i}d^p_{\pm k}$ using PyQUBO?

I am going to implement "turn circuit encoding" method of Coarse-grained lattice protein folding on a quantum annealer(Babej, Ing & Fingerhuth; 2018) using PyQUBO to run on the DWave qbsolv environment. In this method I have to implement equation…
Hasitha Perera
  • 75
  • 2
4
votes
1 answer

Is there any mathematical technique to find the exact solution of a QUBO problem?

Suppose I am given a QUBO problem consisting in the minimization of a quadratic function $\vec{x}^T Q \vec{x}$ over a binary-valued vector $\vec{x} \in \{0, 1\}^n$, with $Q$ a symmetric indefinite real matrix. Is it possible to compute analytically…
SimoneGasperini
  • 1,634
  • 1
  • 3
  • 18
3
votes
3 answers

Is QUBO formulation actually useful for solving real-world problems?

Combinatorial optimization is often mentioned as a potential application of quantum computers. One of the main paradigms here is to reduce combinatorial optimization to an Ising problem, which is mathematically known as QUBO (quadratic unconstrained…
Nikita Nemkov
  • 1,725
  • 6
  • 22
3
votes
2 answers

Optimizing SymPy Implementation of prime factorization in form of QUBO

I'm trying to reproduce a paper on Prime Factorization. This paper converts the problem into a QUBO form, which then we can map it to an Ising Minimizer. I've basically done everything, and I've obtained the final QUBO expression of page 3. My only…
Amirhossein Rezaei
  • 151
  • 4
3
votes
2 answers

Inequality constraint to QUBO penalty

I am trying to formulate a problem as QUBO problem and am not able to transform the inequality constraint. $$ \sum_i^N x_i \geq 1 $$ into a suitable penalty function. For N = 2, the penalty term can be written as $$ P(1-x_1-x_2+x_1x_2)$$ as…
Rogue8989
  • 31
  • 2
3
votes
1 answer

Penalty formulation regarding inequalitties

During the formulation of a QUBO matrix I have a question regarding penalty formulation. Once I'm done with QUBO formulation such as $x_{i}Ax_{j}$ where A is the QUBO matrix, $x_{i}$ and $x_{j}$ are binary variables. However, the variables $x_{i}$…
Kai-Chun Lin
  • 265
  • 1
  • 7
3
votes
1 answer

Can any binary problem be solved by a QUBO?

As far as I know, if a computing problem can be solved by the quantum annealing approach, it also means the solution space should be binary, e.g., a vector that only contains either 0 and 1. Otherwise, there are no further conditions, correct? Since…
Kai-Chun Lin
  • 265
  • 1
  • 7
2
votes
2 answers

Question about QAOA for MaxCut, and adiabatic evoution

I'm experimenting with QAOA for solving some MaxCut instance, and I think I see conflicting explanations online and in the literature. Incidentally, I fail to reproduce the nice decreasing cost/iteration curve of…
cocompletehippopotamus
  • 59
  • 4
2
votes
1 answer

How to map QUBO to Ising and account for the sign change in non-diagonal elements?

A question that has been bugging my mind in quantum annealing is: Assume we have a QUBO matrix $Q_{ij}$ with non-zero non-diagonal elements which have different signs, that is $Q_{ij}<0$ for some $i\neq j$ and $Q_{nm}>0$ for some $m\neq n$. How can…
Nikolaos Petropoulos
  • 21
  • 2
2
votes
0 answers

How to choose the initial parameters beta and gamma for QAOA classical optimization stage

I read in this question that the initial parameters are chosen randomly, however this can lead to choosing a set of parameters that lead us to be stuck in a local minima. In this pennylane tutorial they state while solving the Minimum Vertex Cover…
yousef elbrolosy
  • 337
  • 1
  • 9
2
votes
1 answer

Is there a QUBO solving Q-algorithm with proven superpolynomial speedup - even for only a subclass of QUBOS?

Is there any known quantum algorithm that solves a specific subclass of QUBOs (with the subclass, I mean that certain constraints are being imposed on the QUBO model, e.g. sparsity of the QUBO matrix) has a theoretically proven superpolynomial…
qubitzer
  • 934
  • 11
1
2 3