Talk:Quantum computer

From Wikipedia, the free encyclopedia

This article is a former featured article removal candidate. Please see the archive to see why its featured status was upheld.

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.

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.

Contents 1 Question 2 Request for references 3 Boondoggle 4 Bias towards NMR 5 Quantum Computers work while without power? 6 Merge request from Quantum algorithm 7 Superior to classical computers? 8 How does Shor's algorithm work? 9 Simplification required 10 DNA computing - better to omit it? 11 "Asymptotically"? 12 NP problems 13 This article Rocks

[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 / 2^N, 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 [1] or [2]. -- 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?

[3] 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)

[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)

[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.

[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)

[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)

[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)