23
votes
Accepted
Did D-Wave show quantum advantage in 2023?
A clear case of quantum advantage
Google's quantum group demonstrated quantum advantage with a much earlier version of D-Wave hardware in the following figure from a 2016 paper, in which the D-Wave ...
6
votes
Accepted
Is there any mathematical technique to find the exact solution of a QUBO problem?
The short answer: QUBO problems are known to be NP-hard. So, there should be no analytical solution.
The long answer:
You seem confused about solving quadratic problems, eigenvalues and the meaning of ...
- 3,284
4
votes
Accepted
Can D-Wave machines solve QUBO problems more efficiently than gate model devices?
This cannot yet be tested for more than about 100 qubits, since no publicly announced circuit-based quantum computer has been built with more than 127 qubits.
Furthermore, the word "efficiency&...
4
votes
Did D-Wave show quantum advantage in 2023?
The answer that @user1271772 gave is quite comprehensive - however I think that there are at least a few additional important papers which give arguments on the topic of the current capabilities of D-...
- 726
3
votes
Is QUBO formulation actually useful for solving real-world problems?
There are several important classes of problems that are well-suited to QUBO, such as quadratic assignment problems, Max-Cut, and graph coloring, to name a few. For these types of problems, it is ...
- 3,284
3
votes
A highly space-efficient embedding of prime factorization problem using the Ising model
Please tell what you think about my approach.
There have been several papers doing basically what you are doing. Create a multiplication circuit whose ground state is the factoring solution. Apply ...
- 42k
3
votes
Accepted
How to apply the QAOA in such a QUBO problem?
This problem is known as the Currency Arbitrage Problem. This white paper shows how to formulate it as a QUBO.
The white paper is talking about solving the problem using a quantum
annealer. Of course, ...
- 11.8k
3
votes
Optimizing SymPy Implementation of prime factorization in form of QUBO
First of all, I read the paper and it seems that the values of l1 and l2 are wrong for ...
- 283
2
votes
Grover's algorithm to maximize QUBO functions
It seems that you confused two approaches. First one is quantum annealing which can be implemented in single purpose quantum processor like those offered by D-Wave. Moreover, variational algorithms ...
- 14.9k
2
votes
Accepted
Is there a QUBO solving Q-algorithm with proven superpolynomial speedup - even for only a subclass of QUBOS?
In optimization, we usually care about the relative scaling of some runtime criterion with respect to the problem size $n$.
Some optimization algorithms (classical or quantum) might have a nice ...
- 3,284
1
vote
Accepted
Quantum optimization: Number of needed auxiliary variables to reduce higher order terms
Lets say we have the cubic term of binary variables $xyz$. We can reduce the order by introducing an additional binary variable, $w$, which we constrain to satisfy $w= y \times z$. We now replace $xyz$...
- 556
1
vote
Is QUBO formulation actually useful for solving real-world problems?
I think this is a general problem we're struggling to deal with. We take a problem that exists as a MILP (like your one) which has a lot of rich structure that can be exploited by classical solvers ...
- 556
1
vote
Inequality constraint to QUBO penalty
It would help if you used slack variables and squared penalties. One way of doing it is by defining the following penalty
$$P\left(\sum_{i=1}^{N}x_i - 1 - Z \right)^2,$$
where $Z$ is an integer ...
- 3,284
1
vote
Grover's algorithm to maximize QUBO functions
"I've been told to encode this cost function which I'm not sure of. And to use quantum annealing to maximize the cost function."
Grover's algorithm is a circruit-based algorithm. It uses ...
1
vote
Optimizing SymPy Implementation of prime factorization in form of QUBO
To make it fast, I would guess a good option is to ditch sympy and simply use a dictionary and strings to create the QUBO, probably something like dic[(x_1,x_2,x_3)] = alpha_(x_1,x_2,x_3) which takes ...
- 27
1
vote
How to convert QUBO (with non-zero diagonal elements) to Maxcut?
It is well-known that any QUBO problem can be translated into an equivalent maximum cut problem (MaxCut), see ref 1. Given a weighted graph ( G = (V, E) ) with edge weights ( w_{ij} ), where ( ij \in ...
1
vote
Accepted
Mapping a QUBO onto an observable for use with Qiskit QAOA
First of all, you will need to convert your problem into a QuadraticProgram
...
- 11.8k
1
vote
Convert Hamiltonian to Ising Formulation or QUBO
Given that you decompose your matrix into a sum of Pauli operators such that there are no instances of $X$ and $Y$ (so basically a Pauli sum of $Z$, $I$ and any tensor product of these two), you can ...
- 2,965
1
vote
Inequality constraints on D-Wave (using PyQUBO)
First of all, since you mention D-Wave in the title, I want to mention that the slack variables need to be constrained even further than you showed in your question. Specifically, your $N$ has to be ...
Only top scored, non community-wiki answers of a minimum length are eligible