Talk:BQP

This article was the subject of a Wiki Education Foundation-supported course assignment, between 19 January 2022 and 13 May 2022. Further details are available on the course page. Student editor(s): Prss98 (article contribs). Peer reviewers: Yllenerad, Terence9915.

Decision problems?

Surely most of the examples given are not decision problems but function problems? Like computing the Jones polynomial at a root of unity, you want a number; or simulating a quantum system, you want a set of probability amplitudes? 129.234.252.66 (talk) 16:56, 29 January 2014 (UTC)

Untitled

Is the number of qubits of the quantum computer held constant or may it vary with input size? --AxelBoldt

I think it is assumed that there's always enough of them, just as we do with Turing tapes. --Seb

---

What does this 1/4-clause mean in long run ? That chance of failure in many runs is (1/4)^N, 1/2*(1/2)^N or what ? --Taw

The probability that the algorithm fails N times in a row is (1/4)^N. Actually I think 1/4 is more or less arbitrary; choosing any other (rational?) number in ]0,1/2[ would not change the class. --Seb

Right. It works for irrational numbers too. But not complex, quaturnion, or surreal. :-) --LC

---

i removed the paragraph "Because randomness is inherent in quantum computers, there is no notion of deterministic algorithms, such as those implemented by ordinary Turing machines. This makes BQP the primary class of practical quantum algorithms that is studied." it is possible to have quantum algorithms that end in an eigenstate of the measurement basis. these algorithms give the same output every time, so they are not "random". neither is the process of running the algorithm, since quantum dynamics is deterministic in the absence of measurement. cheers. -- dave kielpinski

Is it 1/3 or 1/4 ?

I don't speak Spanish or German but when I go to those other pages I do see the fraction 1/4 used instead of 1/3.

Doesn't matter; they give the same class. 209.210.225.6 03:59, 8 April 2007 (UTC)

Weird statement

This is the informal argument used in the text of why BQP is low for itself: "Informally, this is true because polynomial time algorithms are closed under composition. If a polynomial time algorithm calls as a subroutine polynomially many polynomial time algorithms, the resulting algorithm is still polynomial time."

It seems that this argument is wrong: consider an algorithm A that on input a string x outputs xx (i.e. A(x) = xx) and consider the result of an application of A to itself n times, n is the initial length of x i.e. n = |x|. In other words compute A(A(A(...A(x)...))), the result is clearly exponential.

So imagine an algorithm that, on input x of length n, calls polynomially many algorithms A_1, A_2, ..., A_n as subroutines, each A_i running in poly-time on "its input" as follows: the input on A_i, i <= 2 <= n is the output of A_{i-1} where each A_i is the previous A (on input x output xx).

Clearly the resulting algorithm is exponential on the input x (the output has length 2^n). — Preceding unsigned comment added by Psyspin (talk • contribs) 21:16, 22 February 2013 (UTC)

Your example is not the correct interpretation of BQP with a BQP oracle. Consider two poly-time algorithms, A and B, such that A can call B as a subroutine at unit cost. In this scenario, you can claim that there is another algorithm C that runs in polynomial time and simulates algorithm A. --Robin (talk) 23:43, 24 February 2013 (UTC)

Sure! I'm just commending on the sentence, not on the result. If the cost is unit, as we assume in the oracle scenario, then it's fine. My comment is only about this sentence which seems apparently false in the general setting (again: not in the oracle setting). — Preceding unsigned comment added by Psyspin (talk • contribs) 19:24, 25 February 2013 (UTC)

Is your objection to the sentence "If a polynomial time algorithm calls as a subroutine polynomially many polynomial time algorithms, the resulting algorithm is still polynomial time."? That seems right to me too. The first polynomial time machine, A, is allowed to call as a subroutine polynomially many (say p(n) many) algorithms B_1, B_2, ..., B_{p(n)}. These algorithms are not allowed to call other algorithms as subroutines. This is different from your example. --Robin (talk) 23:30, 25 February 2013 (UTC)

Quantum computer time complixity

It should be stated that quantum computer time complexity doesn't measure actual time but "computational steps". as far as i know the "computational steps" in quantum computer is the number of unitary quantum gates. However the link attached is for Boolean gates complexity class which is a totally different thing. How can we compare the number of Boolean gates to the number of unitary quantum gates? (like comparing oranges and bananas ) and put it in the same world diagram of P and NP ( which is about different Turing machine computation step (head movement )? Boolean gates delay time is much different thing than Unitary quantum gates delay time ( such a thing even exist ? ) — Preceding unsigned comment added by 109.64.143.94 (talk) 09:59, 4 June 2014 (UTC)

Unclear section on the relationship between BQP, P and NP?

The text claims that we know $NP\not \subseteq BQP$, and also $P\subseteq BQP$. But at face value, this seems to imply $P\neq NP$. Proof by contradiction: If $P=NP$ then $NP=P\not \subseteq BGP$ by the first claim, and $P\subseteq BGP$ by the second claim, which is absurd. Given that I doubt I have suddenly solved the P = NP problem, something is clearly wrong here. Can anybody explain this better? 46.5.172.98 (talk) 04:07, 16 May 2021 (UTC)

P and NP

Hey Saung Tadashi, in the bit where it says

"This conjecture is especially notable because it suggests that problems existing in BQP could be classified as harder than NP-Complete problems. Paired with the fact that many practical BQP problems are suspected to exist outside of P (it is suspected and not verified because there is no proof that P  NP)"

if I understand right, it should say "There is no proof that P = NP)" because the equality, together with the conjectured $BQP\subsetneq NP$ would imply that $P\subset BQP$ which is to say that quantum computing is more powerful than classical. However, it says "P NP" which looks like a typo to me. I am not an expert in complexity theory, but why did you undo my edit? --Homo logos (talk) 23:41, 25 September 2022 (UTC)

Hi @Homo logos, you are right. My bad, I just saw the edit at L72 and concluded that the entire edit was an accidental edit. I will undo my edit and just fix the typo at L72. Saung Tadashi (talk) 20:50, 26 September 2022 (UTC)