# Quantum algorithm to determine the existence of a solution

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 ?" ?

"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)

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