Talk:BQP

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Mid Priority
 Field: Discrete mathematics
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 

Decision problems?[edit]

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[edit]

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 ?[edit]

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[edit]

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 (talkcontribs) 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 (talkcontribs) 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[edit]

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)