Talk:Quantum computer

From Wikipedia, the free encyclopedia

 This article is undergoing a featured article review to ensure that it meets the standards of a featured article. Please add a comment to assist the process and/or be bold and improve the article directly. If the article has been moved from its initial review period to the Featured Article Removal Candidate (FARC) section, you may support or contest its removal. When the review is complete, a bot will update the article talk page.
Featured article star Quantum computer is a featured article; it (or a previous version of it) has been identified as one of the best articles produced by the Wikipedia community. If you can update or improve it, please do.
WikiProject Physics
Portal:Physics
 Physics Portal
This article is within the scope of WikiProject Physics, which collaborates on articles related to physics.
Featured article FA This article has been rated as FA-Class on the assessment scale.
??? This article has not yet received an importance rating within physics.

This article has been rated but has no comments. If appropriate, please review the article and leave comments here to identify the strengths and weaknesses of the article and what work it will need.
This article is part of WikiProject Technology, an attempt to better organize information in articles related to technology. If you would like to participate, you can edit the article attached to this page, or visit the project page, where you can join the project and/or contribute to the discussion.
It is requested that a photograph or photographs be included in this article to improve its quality.
This article has been selected for Version 0.5 and the next release version of Wikipedia. This Engtech article has been rated FA-Class on the assessment scale.

Archive 1

Contents

[edit] breaking news - d wave quantum computer

D-Wave demonstrated their 16 qubit quantum computer today.

[1] for more info, specifically World’s First Commercial Quantum Computer Demonstrated

I think the way this information was included should be changed or perhaps removed. It sounds more like a PR release instead of something in an encyclopedia article. Very Quiet 13:50, 16 February 2007 (UTC)

  • added newslink about skepticism over dwave actualyl doing any quantum calculations --ManoliIsFat 07:22, 28 February 2007 (UTC)

[edit] Randomised?

The article claims "Quantum computers only run randomized algorithms". I don't believe this to be a true statement. For example quantum error correction is completely deterministic in the sense that if the input is quantum data corrupted by noise within a certain threshold the output is fully determined. Sigfpe 21:33, 20 March 2007 (UTC)

[edit] Question

I was just wondering which sense of the word "dimension" was used in, when talking about the set of states. It would be n if it's the vectorial dimension of the states, 2n-1 if talking about the number of free functional parameters available as coefficients (amplitude and phase except the last one fixed by normalization), 2^something if talking about set theory with something as a function of n. Where does 2^n+1 -2 come from? Thanks a lot.

  • See the section "Can quantum computers ever be practical for factoring?" in the archived talk page for a discussion of the dimensionality of the set of states. The short answer is that a quantum register is described by 2^n complex numbers. But the normalization constraint means that we actually need only 2^n-1 complex numbers. Or if you want to talk about the number of real numbers needed, just multiply by 2 to get 2^n+1 - 2.Bjohnson00 17:52, 29 May 2006 (UTC)

[edit] Request for references

Hi, I am working to encourage implementation of the goals of the Wikipedia:Verifiability policy. Part of that is to make sure articles cite their sources. This is particularly important for featured articles, since they are a prominent part of Wikipedia. Now this article has an extensive list of additional material, but list of further reading is not the same thing as proper references. Further reading could list works about the topic that were not ever consulted by the page authors. If some of the works listed in the that section were used to add or check material in the article, please list them in a references section instead. The Fact and Reference Check Project has more information. Thank you, and please leave me a message when a few references have been added to the article. - Taxman 19:18, Apr 22, 2005 (UTC)

  • I am embarking to add some references to this article in coming weeks. So expect to see a bunch of edits from me. After adding a first reference to an arXiv paper I noticed that I used a different citation style for arXiv than has been previously done in the Further reading section. Is that style the accepted standard for arXiv references on Wikipedia? --Bjohnson00 16:17, 10 May 2006 (UTC)
    • Found the arXiv template, reference updated accordingly.--Bjohnson00 17:27, 10 May 2006 (UTC)

[edit] Boondoggle

I think that QC is a boondoggle. I say this with a heavy heart, as I was quite entranced by it as a postdoctoral researcher in Hans Mooij's group at Delft, working on single electronics circuits.

The theory is beautiful and elegant, and the possibilities are incredible-- and I mean "incredible" as in "not credible". In order to implement the kind of operations such as in Shor's algorithm, you have to rotate the "qubit vector" by, for example, turning a signal on and off, such as the gate voltage employed by Nakamura et al.. The problem is that you need to be able to rotate the vector by 2Pi / 2N, which translates to duty cycle times far below a nanosecond for solid-state systems (which are scalable) even at liquid helium temperatures.

No you don't need to rotate to accuracy 2Pi/2^N. Errors in quantum gates ADD, therefore to achieve constant accuracy for a polynomial sized algorithm you need accuracy which is basically one over the size of the algorithm. For Shor's algorithm, for example, to factor a number of size N, you need an accuracy of order 1/log^c(N), where c is around 2. Further, you never need in quantum computation to have a duty cycle (clock) which scales like this: you need only a universal set of quantum gates: "higher phase gates" are then made out of the these gates. To understand why accuracies don't build up in such constructions, you then need to understand why fault-tolerant quantum error correction works.

I would love to be proven wrong, but after being in the trenches for a while and an observer since then, I've lost faith in QC. Keeping 10^3 - 10^4 qubits coherent in any sort of man-made environment seems irreproducible at best.

Austin Fowler showed that Shor's algorithm still works if you skip rotations smaller than π / 64, see [2] or [3]. -- Tim Starling 06:53, 4 April 2006 (UTC)


Sounds alot like the situation with nuclear fusion power. Lots of promise, no reason theoretically it can't work, lot's of smart physicists devoting their careers to it... yet it's somehow always 20 years into the future.

Yes, except that the payoff for society is vastly lower. Nuclear fusion would provide a clean, cheap, renewable energy source. Quantum computation would provide the ability for particularly wealthy governments to snoop on the communications of citizens. Most of the money comes from defence, so other applications haven't been seriously developed. Some have suggested that quantum computation would provide gains for computational chemistry and related fields, but such applications are certainly far more complicated than factorisation. -- Tim Starling 11:24, 12 April 2006 (UTC)
Actually I think that gains in computational chemsitry are actually a lot less compicated than factorization. For example recent work in Martin Head-Gordan has shown that quantum computers with around fifty qubits will beat todays classical algorithms (as opposed to in the thousands for breaking todays codes.) Dave Bacon 20:55, 28 April 2006 (UTC)

[edit] Bias towards NMR

This article seems to have an unfair bias towards the NMR implementation (simply in the amount it covers and refers to it, and even the first picture at the top), while there is yet no separate page on NMR quantum computing. Would it be possible to move the NMR info into its own article without detracing from the content of this? I appreciate it would be harder to explain some of the concepts without a particular implementation in mind...

And yes, it's obviously an interdisciplinary field, so it's impossible to separate everything out nicely. Tomatoman 20:12, 6 January 2006 (UTC)

I agree that this article focuses too heavily on NMR implementations. In particular, the section on "initialization, executation, and termination" includes a discussion of ensembles which is only valid for NMR, and so should be moved into an article just on NMR quantum computing.--Bjohnson00 23:08, 6 March 2006 (UTC)

[edit] Quantum Computers work while without power?

[4] Contemplating exactly what this link entitles; I'm somewhat in the dark. I am assuming however that the architecture of the quantum computer is such that its program works on the photon level without electrons? Meaning, they aren't bombarded by the energy current from a wire and this is what they mean by "switched off" but on the quantum level, natural photon movements interact with the architecture/program without the need for conventional energy? Or is this purely a software phenomenon (but even then, "running" at the proxy software level requires a movement of electric current i.e. electrons correct?). My hope is someone who knows more than me may be able to add the "working while off" phenomenon of quantum computers as per the link to the article here. Nagelfar 22:47, 24 February 2006 (UTC)

In case you want a quicker answer, post your question at Wikipedia:Reference Desk/Science

It's my understanding that binary computers can have two states in their transistors: on or off, while quantum computers have 32 different states. Isn't this a better way of describing it rather than have all those numbers?

It's always wise to view these kinds of results with skepticism, especially when they have passed through the hands of New Scientist, which aims to spin scientific results to sound as weird as possible, taking them to the limits of plausibility and often beyond. The Nature article makes a bit more sense, although the full text is not freely available.
The procedure for this kind of experiment could be more matter-of-factly described as follows:
  1. Run the algorithm on the input data
  2. Simultaneously, pass the input data through without running the algorithm
  3. Interfere the results of 1 and 2 in quantum fashion
  4. Contrive your measurement so that your detectors only pick up something if the result of the algorithm has some particular value and the particle being measured came through the non-running arm of the experiment. Particles which went through any other path are discarded without being measured.
Despite the fact that the particle being measured didn't have the algorithm run on it, the running of the algorithm is absolutely necessary to obtaining the correct result. If you switched off the power to the algorithm unit (if it requires power) or removed it, the device would immediately stop working. This is because particles from the "running" part of the device interfere with the path of particles from the "non-running" part of the device. That this is possible is easier to understand from the point of view of wave propagation rather than the Copenhagen interpretation, so predictably, the popular press chooses the latter. Under the Copenhagen interpretation, one might claim with a straight face that the particle from the running half of the experiment never existed, and that the particle from the non-running half was perturbed by some kind of magical knowledge of the workings of a distant computer. This, I would argue, is misleading. -- Tim Starling 02:55, 17 April 2006 (UTC)


[edit] Merge request from Quantum algorithm

This is the entry:

"A quantum algorithm is an algorithm designed for use on a quantum computer." (and some links) Ripper234 20:49, 2 April 2006 (UTC)

Agree. Dictionary definition doesn't warrant its own page at this time. --Officiallyover 04:36, 3 April 2006 (UTC)
Moved. Ripper234 15:44, 3 April 2006 (UTC)

[edit] Superior to classical computers?

There is one other problem where quantum computers have a smaller, though significant (quadratic) advantage. It is quantum database search, and can be solved by Grover's algorithm. In this case the advantage is provable. This establishes beyond doubt that (ideal) quantum computers are superior to classical computers.

Doesn't this just establish that ideal quantum computers are superior to classical computers for dabase search, and not in general? Or am I missing something?—Matthew0028 17:56, 4 May 2006 (UTC)

Its true that not every classical algorithm has a (known) "accelerated" quantum equivalent. However, since a QC could always be run in classical mode, its never slower than a classical machine. There are other problems which are so slow for a classical machine as to render them impossible altogether, such as factoring. But thanks to Shor's factoring algorithm, factoring large numbers is entirely feasible in a quantum one. Finally, you shouldn't knock database search - the problem is extraordinarily general. The basic techniques can be applied to search space problems, meaning that classical problems that can only be solved by brute force are accelerated in a QC.

So the basic point is, "A QC is frequently faster, and never slower."--Hyandat 03:31, 5 May 2006 (UTC)

I think that this article is clear on what QC can do better than classical computers, but it never mentions on WHY it is better...what makes it better than classical computers? How is it that these algorithms can be run on QC and not classical? how about its ability to do parallel computations? or the significant gain in using resources like memory? Janechii 11:31, 8 May 2006 (UTC)

[edit] How does Shor's algorithm work?

How does Shor's algorithm work? Our article on this subject currently contains the view of David Deutsch, which he happens to view as proof of the many worlds interpretation of quantum mechanics. Are there are any other interpretations of how it physically works, by physicists (as opposed to internet amateurs?) If so, these other POVs should be added to the Shor's algorithm article. RK 20:30, 11 June 2006 (UTC)

http://en.wikipedia.org/wiki/Shor%27s_algorithm#How_does_Shor.27s_algorithm_work.3F

Maybe the section should be called "Why Shor's algorithm works", since how it works is described in that article. Even the question "why" is really equivilent to "Why does quantum mechanics work?" since noone who believes in quantum mechanics can deny Shor's algorithm - it follows logically and provably. I'm not sure anyone today can answer "Why QM?" rightly. That's just the way things work. If you wonder what aspect of quantum mechanics makes Shor's algorithm faster than any possible classical algorithm, I think the right answer is entanglement. Turing machines are hopelessly local, and so can never properly do entanglement, which is nonlocal. In terms not unfamiliar to computer scientists, quantum computers can delay the resolution of a complex sequence of contingencies (by maintaining a superposition) which it can later resolve instantaneously, with no time overhead, upon a measurement (defies locality). Turing machines, being local, will always require at least some time to resolve contingencies, since locality requires there be communication between the various bits (as in the Greenberger-Horne-Zeilinger game).

To the best of my knowledge, this is the only thing a quantum computer can really do that a turning machine is incapable of simulating. In fact, the Gottesman-Knill theorem shows that a quantum algorithm that doesn't make enough use of entanglement can be simulated efficiently. I know I'm not alone in my view that entanglement is the key to this mystery. The explanation as posted under Shor's algorithm seems strange to me, because it seems to suggest we can borrow computing power from other worlds. But in that case, Shor's algorithm would only be accelerated in the world doing the borrowing, so that from our point of view it would only be faster some of the time.--Hyandat 21:34, 11 June 2006 (UTC)

But wouldn't the various worlds essentially be pooling their computeing power for Shor's algorithm? All the worlds are trying to factorize the same number, so each world does their own bit of work and the results interact with all the other worlds with information flowing both ways. Hence all the worlds would experience accelerated computing. Tomgreeny 15:30, 22 March 2007 (UTC)

[edit] Simplification required

Even in the introduction, this article lacks a simple explanation for the novice. I suggest a very simple explanation at the top, that anyone could understand, then progress deeper and deeper into the subject in subparagraphs.Landroo 14:48, 8 July 2006 (UTC)

I agree, a sort of example or very layman's terms explanation of what a quantum computer is, and what it is capable of doing over a present day computer. Eridani 0123, 12 January 2007 (EST)


I am not all convinced that either issue can be further simplified. A QC exploits the unique features of quantum mechanics, so you cannot really understand what a QC is without understanding what QM is, and it is a difficult subject. What a present-day QC can do over a present-day conventional computer is not a lot, but that is a misleading answer. The interest in QC lies in what it could do if developed sufficiently.1Z 15:09, 12 January 2007 (UTC)

[edit] DNA computing - better to omit it?

I don't quite understand why DNA-computers are lumped into the introduction as "classical" computers. At least to my knowledge, DNA computers are anything but classical (e.g., highly parallel and probabilistic and all that). If one really wants to mention DNA-computers, a far more elaborate explanation would be necessary; the way it is phrased now, it's misleading and highly imprecise. I suggest not to mention them at all.

DNA computers are classical in the sense that the word "classical" is being used here. "Classical" is used in opposition to the word "quantum" (common usage among physicists) and DNA computers are classical in this sense. Additionally, there are parallels between DNA computing and NMR spectrography based "ensemble quantum computing" (eg. see [5]). Sigfpe 22:59, 20 March 2007 (UTC)

[edit] "Asymptotically"?

It is widely believed that if large-scale quantum computers can be built, they will be able to solve certain problems asymptotically faster than any classical computer.

I don't understand the usage of "asymptotically" in this sentence. Is the sentence claiming that the speed of classical computers can approach but never reach the speed of quantum computers at solving certain problems? If this is so, then the use of "asymptotically" is simply incorrect, because a curve can in fact possibly reach its asymptote and even cross it. I think that what is really meant is something like "incomparably".--Susurrus 04:43, 27 November 2006 (UTC)

For some problems there exists a quantum algorithm asymptotically faster than any possible classical algorithm. e.g O(n^(1/2)) quantum vs O(n) classical for search. This sentence is correct but impercise "widely believed" should be replaced with "a fact". --kaz

[edit] NP problems

'There is a common misconception that quantum computers can solve NP-complete problems in polynomial time.' I thought they could, can anyone explain this one? Paskari 20:09, 2 December 2006 (UTC)

It hasn't been proven one way or the other. What's there to expain? --kaz

Generally, the assumption is that an NP-complete problem can't be solved by any means other than trying every possible combination; thus it will require fully-exponential time on a classical machine.

Now the problems which can be easily solved on quantum computers also have classical algorithms that run in less than fully-exponential time (ie they use time 2^sqrt(n) or the like), so they probably aren't NP-complete. So we expect that quantum computers also require fully-exponential (or at least more than polynomial) time on NP-complete problems. Grover's algorithm is probably the only one that provides any speedup for a complete problem, and it is only quadratic, so it turns time 4^n to time 2^n, which is not really useful. Ben Standeven 05:27, 29 January 2007 (UTC)

A quadratic improvement on 2^n is 2^[n/2], not 2^[squrt(n)] and is called "subexponential". 24.77.65.236 23:53, 25 February 2007 (UTC)

[edit] This article Rocks

It is not an easy article, and I could see value in some "dumbed down" introduction to make it more accessible to people who are not well-versed in quantum mechanics or computer science.

I am a lowly biologist/biochemist who dabbles in computer programming and materials, and I find this article to be very challenging. But I like that. This article gives me lots of food for thought and points me in lots of good directions. I am very grateful to the editors of this article. And I am impressed by the civility demonstrated here in the Talk section.

Cyclopiano 09:43, 9 December 2006 (UTC)

[edit] Quantum Computers Now Exist, Update Article

I am unable to update the article but if this newspaper is correct a small Canadian company has succeeded at making a Quantum Computer.

Link to article: [6]

Sir On The Edge 23:04, 13 February 2007 (UTC)

Experimental QCs have existed for some time.1Z 23:47, 13 February 2007 (UTC)

The word commercial is all-important here.1Z 01:38, 14 February 2007 (UTC)

D-wave has stated that currently the only thing their quantum computer has over classical computers is the word quantum in it's name. Anyone want to buy a quantum bridge? 24.77.65.236 23:57, 25 February 2007 (UTC)

[edit] List of types of computers incomplete ?

How about putting a short list here and point to other computers. In the text there allready is a list. What should be added to it is the neural computers. Perhaps concepts could be added too like distributed computing

I dont mean the neural math, but the rat brains who can fly an airplane. perhaps it's a sad thing they made rat brains do that. But these days they create brain cell like other cell types. And they can be attached to electronics.

Might be a good ide to also provide some information on what type of problems each computer type is good in. Based on that then can be pointed out where a quantum computer fits in.

I think article could be made more complete by adding more type of problems a quantum computer can solve. Or what kind of math direction is used here. —The preceding unsigned comment was added by 82.217.143.153 (talk) 23:07, 14 February 2007 (UTC).

[edit] What is diferent between Shor’s faktorization algoritm and Grover’s algoritm?

Simple: Grover’s algoritm give answer with better probability than Shor’s faktorization algoritm. If Shor’s algoritm gives answer with probability N, then Grovers algoritm gives answer with (log N)^1.5 better probability. —The preceding unsigned comment was added by 213.190.46.52 (talk) 17:45, 8 April 2007 (UTC).

Retrieved from "http://en.wikipedia.org../../../q/u/a/Talk%7EQuantum_computer_659e.html"