This might help

I have removed a series of comments on some recent posts. I apologize to the posters. In compensation for this removal I offer this. It is a high-level introduction to the computational model which we are working to embody. If you have a comment that has been removed, please read this.

If you have any questions about this computational model, comment away! If you have questions about Grover’s search or anything that’s not explicitly heuristic, I can try to answer but the question/answer are probably not directly relevant to the systems we’re building.

15 thoughts on “This might help

  1. Geordie.The Document you showed is good,but for me reading this is hard and boring.would you just show something that is easy to understand but novelty?

  2. Tell me, how much your building quantum computer speed up tasks, which is not Shor’s algorithm or quantum simulation or discreat log finding, but tasks, which can be performed on curent sistem with 16, 32, 512, 1024 qubits (becouse on your rodmap tasks for QFT, quantum simultion and shor algorithm will be possible running only in 2009 year)? So how much can speed up Orion until 2009 year, whom need or O(N^0.5) time, where N=2^n, and n is number of qubits and number of inputs, or O(n) time, where m=n^2 and m is number of qubits and n is number of inputs, then while for classical computer need O(N=2^n) time, where n is number of inputs? Or maybe need O(N^{1/6}) time or so? Or there is wide range of problems for which ones need more time and for anothers ones needs less time? Then sill tell how much need time for problems which quantum computer can speed up the most better (except shor’s algorithm, quantum simulation and QFT, becouse it will be possible only in later version 2009 year, and I want know how much it speed up for curent version with 16, 32, 512 or 1024 qubits).

  3. Sr,how much speed up is not importment,because it is improving.if dwave showed something can provid their QC can have more than 7 Qbit that means they solved a big problem in building QC,and the Qbit can add as they wish.

  4. combineguard, don’t means, after roughly 20-50 years, quantum computer will be deducated only for quantum simulation. And for solving Grover’s algorithm problems classical computer will be as fast as quantum computer. Becouse for Grover’ algorithm problems time can’t be longer than 10^6 seconds.

  5. sr,We should not say the quantum computer “How fast the quantum computer run” instead we should say”How many data the quantum computer can deal at the same time”.

  6. If you interesting, I can little explain. Adiabatic quantum computer giving approximate answer iinstead probabilities for over types quantum computer. Classical computer giving probabilities. I don’t know how to quantum computer, but for classical computer approximate answer and probabilites is the same. Or you get approximate answer or you many variants checking and after each chek you compare new answer with previuos answer and if new answer is better then save new answer and previuos delete. And after many check you save only one aswer which is the most better from all check answers. For example salesman traveling problem need know, how with minimum road length visit some many cities. So you know what is length from one city to another. So you randomly checking many possible variants and sumate all lengths and give some answer in meters. And after another check you save answer which is better. IF number of cities is very big, then variants can be very much, so randomly checking and saving the best one answer possible get enough good approximte answer like in adiabatic quantum algorithm. If there is very much variants, then to classical computer need check N variants and to quantum computer N^0.5 variants. But if N say is extremly large, say 10^100,. then nor quantum nor classical computer can give the best answer, but both can give approximate answer (enough good answer). So time can’t be more than 10^6 s and if quantum and classical computer working at same speed say 1 GHz, then time can’t be more than 10^15 seconds. And quantum computer running Grover’s algorithm can’t do more than 10^15 iterations. So if 10^100, then classical computer will give approximate answer, which rating is r/N=10^{-85} and quantum computer approximate answer ratign will be (r^2)/N=10^{-70}. The better rating the better answer. Ofcourse for problem with more variants need also and more qubits. And for classical computer little bit harder claculate more bits string, but for quantum computer need increase calculation accuracy linarly with qubits and for classical computer need increase power linearly with bit string long, so there they both equal. And don’t matter how big will be problem and how big will be number of qubits to overcome this problem, to classical computer will be need increase speed linearly-equal with number of qubits in quantum computer. So only one superiority has quantum computer, which is time, and yes quantum computer is (10^{-70})/(10^{-85})=10^15 times faster than classical computer with 100-1000 transistors. But classical computer can have 10^9 and more transistors. And then more transistors is in classical computer the more equal quantum and classical computers are. Number of qubits in quantum computer for Grover’s algorithm problems, don’t help quantum computer to be faster than classical computer, and for classical computer need increase speed the same as need increase number of qubits (for example, if in quantum computer increase qubits form 100 to 1000, then classical computer speed need increase only 10 times, but for quantum computer need increase accuracy at least 10 times…).

  7. sr.thank you for writing so many words for me.i really appreciate.from your word i know you are a expert on math and calssical computer.(BTW,i am a programer)but about quantum computer you should know more.
    the quantum computer is more powerful than you think. take your salesman for example:classical computer will send a salesman try every possible way, the more city the more time.but for quantum computer it not work like this,it will send a lot of salesmen to try every possible way and the all of the saleman feedback length he moved then we can get the shortest way.
    so you know the quantum computer not need time,but depend on number salesman it can sent
    How many salesmen the quantum computer can send depend on the how many qubit it have.for example : 5qubit quantum computer can sent 2^5 salesmen at same time.7qubit quantum computer can sent 2^10 salesmen at same time.

  8. but with 5 qubits need do (2^5)^0.5 Grover’s iterations or steps (for classical computer need 2^5 steps), for 7 qubit quantum computer can sent 2^7 salesmen at same time, but must do (2^7)^0.5 steps, while classical computer must do 2^7 steps.
    And now try to imagine how much steps need for qubits 200 qubits? It need (2^200)^0.5=(10^60)^0.5=10^30 steps. If quantum computer working at 1 GHz then need 10^21 seconds or 10^14 years. Ofcourse you can say, that for smaller problem need much less steps, but I guess, this claim is wrong (I such claim found only in one paper 2000 year, where about adiabatic quantum computer was thoughts, that it can’t speed up somthing and I now can’t find this paper, and in 2001 newer paper I found, that that was saying in 2000 is wrong…). So I in one paper or 2000 or 2001 year about adiabatic quantum computer found, that only n time and n^2 qubits, while for classical computer need 2^n time. But I don’t know maybe some gay wrote paper who don’t understand that he talking… But if it will be like I say now, then I think, many quantum teoretics will recal Grover’s search algorithm not quadratical speedup, but exponentional speed up. And if you interested how much quantum algorithms is, I can say, that only two: Grover’s algorithm and quantum simulation. Shor algorithm is just power demonstrating algorithm and use the same quantum furier transform like quantum simulation. Deutsch josza algorithm is also only power demonstration. So algorithm’s, which can make many is only two Grover’s and quantum simulation, another all algorithms is needed for shor algorithm or so, like discreat log or period finding (for shor algorithm). Shor’s algorithm also can make many, but only in ilegal way and instead factoring can be quantum cryptography or another classical puzzle some algorithm, which can replace RSA.
    So if you asking how much time need to solve salesman problem with say 2^512 variant, and if you have 2048 qubits quantum computer, which can be in 2^2048 states superposition, then I can you say this: still will be need (2^512)^0.5 steps (if not (2^2048)^0.5 steps). Becouse if it will be possible solve 2^512 problem with 2048 qubits, per polinomial (per few seconds or so) time, then I am abou 99% sure, that Grover’s algorithm would be called exponentional speed up and not, quadratic or square root time.
    So for biger quantum computer (with more qubits) need also and bigger problem or then quantum computer don’t exploit all his power.
    So then through this formuls for classical computer r/N and for quantum computer (r^2)/N, you can understand that quantum computer is better only if number of steps is more. So if number of steps is limited by computation time (you can’t wait 100 years until quantum computer solve you salesman problem better than classical), then just need more classical power and classical computer will be equal quantum computer. r is number of steps. And r can’t be more than 10^15 steps for quantum computer. Becouse if quantum computer working at 1Ghz, then to him need (10^15)/(10^9Hz)=10^6 seconds = 11 days. For classical computer to have the same speed as quantum computer need r^2 steps, so need (10^15)^2=10^30 steps. And working at 1GHz for classical computer would be need 10^21 seconds. If classical computer have many transistors, then need less time about 10^12 seconds and if in future number of transistors increase, then will be need less time and if classical computer consist of many procesors then need also less time, until time needed time for quantum and classical computer will be the same.
    Also you probabily think, that if quantum computer consist more qubits, then it is exponentionaly better than classical computer. No,it would be better if both classical and quantum computerswill work very long (now I am talking exlusively about Grover’s algorithm).
    Here examples (this formula is 100% good for large N):
    ((r^2)/N)/(r/N)= how much quantum computer is better than classical computer. Where r is number of steps ( and it is for both quantum and classical computer is 10^15) and N is 2^n, where n is number of qubits and N is problem size. So if you insert any N value and r value always is the same: 10^15, then you always will calculate, that quantum computer is better than classical computer 10^15 times if classical computer don’t have many transitors. So more steps is imposible for quantum computer, but more transistors is possible for classical computer and so in future after maybe 30 years classical computer will has very much transistors and will be as fast as quantum computer, which using Grover’s algorithm.

  9. sr,i really like you.if you in china i like add you to my term.man can such focus on a problem was honorable.

    yesterday my explain not clarity. if salesman a quntum computer can sent no more than different ways can try,we can say:”this quantum computer can not solve the problem!,we need one can sent enough salesman(qubit)” to solve Grover’s algorithm we need more than 1000qubit.

    quantum computer work just once,and this process need no time.for quantum computer just one question qubit enough or not.if a document or paper say how “fast” quantum computer is or a time quantum computer it need,you can know he/she is telling a lie

  10. For quantum simulation it is absolute right, but for Grover’s algorithm it is absolute wrong. Becouse for quantum simulation even 20 qubits quantum computer will be faster than supercomputer. And for Grover’s algorithm I can’t guaranty you 100%, that it is like I saying, but I think, that it is exatcly like I am saying (type in google grover algorithm). Maybe I am not somthing yet understanding, maybe for classical computer need more space on HDD, but I don’t think like that, becouse classical computer randomly checking many variants and after each step saving best one. And like I say maybe for quantum computer to solve 2^1000 variants problem need 2^1000000 qubits. But it still mean, that then possible solve problems, which is untractable for classical computer after about 10^290 seconds. But like I say, if such that, then probably Grover’s algorithm must be called like exponentional speed up giving algorithm, which need quadratic resource (qubits). But Grover’s algorithm is called quadratic speed up algorithm and therefore number of steps fo Grover’s algorithm can’t be more than 10^15 (if it working at 1 GHz). More qubits is better only if you spend also more time, but if you spend time the same as for less qubits, then quantum computer will be better than classical computer the same number of times. And quantum computer still need to solve 2^128 variants problem per (2^128)^0.5 time, if it consist of 1000 qubits. So more qubits don’t solve faster smaller problems (but possible, that solve slower).

  11. combineguard, looks like you are wright. I found, where G. Rose, saying, that for 1000 inputs need 1000000 qubits:
    “…up to say a million qubits, which should be able to encode 10s of thousands of variables…” ( http://room408.wordpress.com/2007/03/06/11-questions-for-geordie-d-wave/ ).
    Then with 40000 qubits quantum computer performing Grover’s algorithm will be faster than classical computer maded from all earth atoms and working the 10^13 years. Quantum simulation is quadraticly faster than Grover’s algorithm. If you want, that Grover’s algorithm give to you the same speed up like quantum simulation or like Shor’s algorithm, then you just need say 10^10 qubits for Grover’s algorithm instead 10^5 qubits for quantum simulation and Shor’s algorithm.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s