Skip to main content
Quantum Computing

Return to Answer

added 105 characters in body
Source Link
MonteNero
MonteNero
  • 3.3k
  • 7
  • 24

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this. Furthermore, if the duality gap is zero and the complementary slackness conditions hold, then, such a QUBO problem could be solved in polynomial time in the Lagrangian dual formulation. So, I guess, this approach could identify a potential subclass of QUBO problems that could be solved very fast.

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this. Furthermore, if the duality gap is zero, then, such a QUBO problem could be solved in polynomial time.

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this. Furthermore, if the duality gap is zero and the complementary slackness conditions hold, then, such a QUBO problem could be solved in polynomial time in the Lagrangian dual formulation. So, I guess, this approach could identify a potential subclass of QUBO problems that could be solved very fast.

added 105 characters in body
Source Link
MonteNero
MonteNero
  • 3.3k
  • 7
  • 24

Coming back to your first question. Take aan $n \times n$ QUBO matrix $Q$ with off-diagonal terms being zero. This is as easy as it gets. The problem is now linear and has no constraints. This can be solved in $n$ steps... by hand... even for large problems. So despite that there are $2^n$ solutions, we find the optimal solution exponentially fast.

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this. Furthermore, if the duality gap is zero, then, such a QUBO problem could be solved in polynomial time.

Coming back to your first question. Take a QUBO matrix $Q$ with off-diagonal terms being zero. This is as easy as it gets. The problem is now linear and has no constraints. This can be solved in $n$ steps... by hand... even for large problems.

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this.

Coming back to your first question. Take an $n \times n$ QUBO matrix $Q$ with off-diagonal terms being zero. This is as easy as it gets. The problem is now linear and has no constraints. This can be solved in $n$ steps... by hand... even for large problems. So despite that there are $2^n$ solutions, we find the optimal solution exponentially fast.

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this. Furthermore, if the duality gap is zero, then, such a QUBO problem could be solved in polynomial time.

Source Link
MonteNero
MonteNero
  • 3.3k
  • 7
  • 24

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 theoretical complexity on paper but have long runtimes that render them less useful. For example, the Quantum Minimum Finding algorithm has Grover-like theoretical complexity for QUBOs. However, when implemented on an ideal quantum computer, this algorithm has unfavourable runtime scaling with respect to $n$, see here. So, its quadratic speedup is only good on paper, but in practice, it has a diminishing value as it takes orders of magnitude longer to sample an optimal solution compared to some other quantum heuristics with no quadratic speedup.

The valid question is which quantum algorithm has a good $\texttt{TTS}$ or $R_{99}$ scaling. Both $\texttt{TTS}$ and $R_{99}$ are the metrics usually used to measure the runtime of quantum optimization algorithms. This is what matters if we are serious about demonstrating that the quantum algorithm $X$ has a speedup over algorithms $Y$ and $Z$.

$R_{99}$ is the number of "shots" (executions of the quantum circuit followed by measurements) that must be performed to ensure a 99% probability of successfully observing the optimal solution. This is defined as: $$R_{99} = \frac{\log 0.01}{\log(1 - P)}$$ In the above, $P$ is the probability of sampling the optimal solution. See this for the derivation.

$\texttt{TTS}$ stands for time to solution. It takes into account the complexity of a quantum circuit and number of times we need to run the circuit to get the result: $$\texttt{TTS} = R_{99} \times t_{ss}$$ Here, $t_{ss}$ is the time in seconds to execute a single shot. $t_{ss}$ usually can be computed analytically by analyzing the circuit structure and knowing the execution time of quantum gates; for example, see here.

What is usually done is plotting $\texttt{TTS}$ against the problem size $n$. In general, for QUBO problems, we will always observe some exponential curve (because of NP-hardness). The question that matters is whether algorithm $X$ has a much nicer $\texttt{TTS}$ scaling than the rest of the algorithms.

Coming back to your first question. Take a QUBO matrix $Q$ with off-diagonal terms being zero. This is as easy as it gets. The problem is now linear and has no constraints. This can be solved in $n$ steps... by hand... even for large problems.

Alternatively, some classes of QUBO problems could be reformulated using the Lagrangian duality theory to obtain much simpler circuits that use quadratically fewer resources, e.g., see this.

As for the second question, I think I already expanded on it fairly in depth. Theoretical speedups are somewhat less important in the optimization community because, despite proven theoretical bounds, algorithms might have excessively high runtimes. Semi-empirical functions like $\texttt{TTS}$ and $R_{99}$ are among many criteria that are worth looking into to quantify speedups.

Also, when considering a certain subclass of an optimization problem and a certain algorithm that can tackle this problem, it is worth remembering the notorious "No Free Lunch Theorems for Optimization". To put the "No free lunch theorem" into the context, consider the following: QUBOs are already a very narrow class of optimization problems. Sure, we can cast many problems into a QUBO form, but then the whole thing becomes a terrible optimization problem; see here for why. So, natural QUBO problems are a very narrow class on their own. Now, you are asking about a subclass of an already narrow subclass of optimization problems, which is QUBO. If there exists an algorithm that can achieve super polynomial speedup in $\texttt{TTS}$ for a subclass of a subclass, then this algorithm must be pretty bad on everything else due to the no free lunch. So naturally, the majority of optimization folks would not be particularly interested in such a narrow algorithm.

Finally, for some radical speedups with "supremacy" arguments on spin glasses, which are usually encoded as a special class of QUBOs, you might want to check out this paper, and note that they use a variant of time to solution as well.