-1
$\begingroup$

$f$ is differentiable (continous) and analytic function.

If $x\in\mathbb{R} \land 0\le x\le1$ then $f(x)$ is computable, $f(x)\in\mathbb{R}$ and $0\le f(x)\le1$.

I have a conjecture that it is possible in O(1) constant time to find the maximum of $f$ in the interval [0,1] by using quantum computer.

Let some qubit be the domain of $f$ and all the values of $x$ where $0\le x\le1$ call this qubit "input" and there is quantum circuit that implements $f$.

At last we need another qubit to be the range of $f$ and call it "output".

Now by using the quantum circuit we can make the output qubit depend on input qubit.

if $y=f(x)$ then $y$ depends on $x$.

The same thing can be done with bits:

Make some bit depend on another bit by using logic/boolean circuit/function.

Now the quantum computer modifies the input qubit so it starts at $x=0$ and changes state towards $x=1$ gradually.

At the same time that $x$ changes so $f(x)$ changes too, so the modification of input qubit also modifies the output qubit respectively.

The quantum computer will use third qubit that stores the maximum of $f$. The third qubit is initialized to zero and the state of output qubit is copied to the third qubit if and only if this operation will increase the value of the third qubit.

I think that this way the maximum of function $f$ can be found in O(1) constant time, maybe even 1 second.

Is my conjecture wrong?

$\endgroup$
  • 1
    $\begingroup$ Don't bother on downvotes, make a lot of good answers. If you have some hundreds of rep (like you have on the SO), nobody will bother to harass you (because it is hopeless). However, if you complain against it on the meta, then you will likely get a lot of downs also on the meta, but the harassment on the main site significantly reduces. Another important thing: listen what they say on the meta, and follow it, mostly you can find a good compromise between your wishes and theirs!. Good luck! $\endgroup$ – peterh Aug 21 '17 at 1:14
  • 1
    $\begingroup$ I agree. I posted about it something on the meta SE (I suggested that explained downs should be stronger). I got around 15 downs, and an incompetent "answer" from somebody who didn't even understand what I suggest. After that, I deleted the question in the last moment until I could (you can delete your own question if it doesn't have multiple answers or upvoted answer). Go to the meta, and ask them. Your survived questions don't seem very bad to me, I can't see your deleted ones, but seeing your reputation I think they were deeply downvoted. $\endgroup$ – peterh Aug 21 '17 at 1:30
  • 1
    $\begingroup$ Specifically, most of the sites have a negative side of their collective community behavior. On the SO, I think it is that the community wants to get rep, but without actually helping you. To get results, you have to fight them. The CS is not so bad, I think they simply don't believe that you are competent. It is much easier to deal with, get a lot of reputation by writing many good answers. So they will accept you. Also fighting on the meta helps on the main site (the price is that you get a lot downs on the meta, but it doesn't affect your reputation). $\endgroup$ – peterh Aug 21 '17 at 1:43
  • 1
    $\begingroup$ It was the meta.stackexchange.com, on that site, yes there is rep. But it is a common meta site for the whole SE. The meta site specific to the cs.stackexchange.com is the cs.meta.stackexchange.com, on that site there is no question/answer ban and the downs don't affect your rep (on the CS SE). "Fight" don't mean real flamewar-ing, I understand only that if you find an evil/unjust behavior, you start a talk about it. Induvidual people are different, but the collective behavior of the communities is that they never retreat in the specific case, but they will be more lenient in the future. $\endgroup$ – peterh Aug 21 '17 at 1:52
  • 1
    $\begingroup$ I made my SE "career" that I answered a lot posts first. Only much later asked I questions. You can get out from the answer ban if you edit your downvoted questions and then they get some ups (maybe 2 is already enough). There is probably also a timeout, maybe some months. Btw, I think the CS SE is really a hardcore site, not for us who made some CS courses in an MSc, but for people working with it every day. I think I could survive here, but I should dig deeply into hardcore CS questions for that. So I am satisfied with my $\approx$ 200 rep here and leave them in peace. $\endgroup$ – peterh Aug 21 '17 at 2:04
3
$\begingroup$

Yes, it's wrong.

First, you seem to be under the impression that you can say "hey, you qubits be the output of $f$ applied to these qubits" in some kind of permanent sense. Like, the output updates as the input is operated on. That's not how entanglement works. The best you can do is compute a superposition of many input/output pairs by applying $f$ to an input under superposition.

Second, you seem to think that you can do comparisons across different parts of the superposition or pull out information without weakening entanglement. You can't. You can interfere different parts of the superposition with each other, but that requires steps like uncomputing the input which you aren't taking into account.

Third, your algorithm has a step where "x changes gradually". That's a big red flag. In particular, this kind of thing always raises the question of "how gradually?". Does it have to get slower as the function get spikier? (Yes it always does.)

Fourth, there is a proof that no unstructured search over $N$ items can be done in less than $\Theta(\sqrt N)$ steps by a quantum computer. It's trivial to translate discrete search tasks into finding the maximum of an analytic function; your proposed $O(1)$ time bound is provably wrong before even looking at the details of your algorithm.

An example of a task somewhat similar to yours, that quantum computers can do faster than classical computers, is computing the gradient of an $N$-dimensional function at a point with one evaluation instead of $N+1$ evaluations.

$\endgroup$
  • $\begingroup$ My $NP\subseteq BQP$ proof has been failed! Thank you for your nice answer. I will believe that $NP\nsubseteq BQP$ until it is proven otherwise. $\endgroup$ – Farewell Stack Exchange Aug 19 '17 at 21:42
  • 1
    $\begingroup$ @ErezZrihen, don't try to prove $BQP\subseteq NP$ as it would be even harder, I think. $\endgroup$ – rus9384 Aug 19 '17 at 22:33
  • $\begingroup$ @rus9384 Your comment implies that your conjecture in your question "satisfiability sufficient condition" is false, because if $P=NP$ then $NP\subseteq BQP \because P\subseteq BQP$ Also $BQP\subseteq NP$ is already true because $P\subseteq NP$. You meant $NP\subseteq BQP$, but not $BQP\subseteq NP$ $\endgroup$ – Farewell Stack Exchange Aug 19 '17 at 22:52
  • 1
    $\begingroup$ @ErezZrihen, my comment implies nothing as it only states that simulating quantumness with non-determinism if it's possible, is not easy. If it's not possible, then proving this is even harder then $P\neq NP$. And $BQP$ vs. $NP$ is open problem. It's not known if they are comparable. It is not even known if $BQP\subset PH$. $\endgroup$ – rus9384 Aug 19 '17 at 23:15
  • 1
    $\begingroup$ @ErezZrihen Non-deterministric Turing-machine. In theory, it is a Turing-machine which can be a set of states, and not only in a state. You can think on it as a hyphotethical CPU with infinite cores. $\endgroup$ – peterh Aug 21 '17 at 1:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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