1
$\begingroup$

Consider two vectors $u$, $t$ living in some space (let's say $ℝ^{n}$), and the following (simple) problem:

Find a vector $v$ such that $∃a,b\inℝ$, $au+bv=t$

Imagine I want to use Grover to find a solution vector $v$.

  • What oracle could I use to mark only states representing a $v$ allowing the existence of such $(a,b)$ values (that I don't need to know) ?
  • More generally is there a way, for some arbitrary equations that can be easily implemented on a quantum computer, to fastly answer the question "is there a solution to this equation ?" ?
$\endgroup$

2 Answers 2

2
$\begingroup$

"Is there a solution to this equation" is the same as asking "Is there a valid assignment of x such that f(x)=1 where f is a boolean function and x is a vector that represents the assignments for the variables in f".

The above is the classical SAT Problem for classical computing. As far as I know, there is no current efficient way to solve SAT using quantum computing (Grover's algorithm is still exponential).

Therefore, I believe the answer to your question is no. (not yet at least)

$\endgroup$
2
$\begingroup$

I would say that from here one goes down the rabbit hole of the halting problem very fast. My answer would be no.

$\endgroup$
1
  • 1
    $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    May 24, 2022 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.