Talk:Quantum computer

From Wikipedia, the free encyclopedia

This article is within the scope of the following WikiProjects:
Former featured article Quantum computer is a former featured article. Please see the links under Article milestones below for its original nomination page (for older articles, check the nomination archive) and why it was removed.
It is requested that a photograph or photographs be included in this article to improve its quality.
The Free Image Search Tool (FIST) may be able to locate suitable images on Flickr and other web sites.
Peer review This Engtech article has been selected for Version 0.5 and subsequent release versions of Wikipedia. It has been rated B-Class on the assessment scale (comments).
Archive
Archives
1

Contents

[edit] Use of NP-complete is wrong

The following paragraph seems wrong:

Consider a problem that has these four properties: 1.The only way to solve it is to guess answers repeatedly and check them, 2.There are n possible answers to check, 3.Every possible answer takes the same amount of time to check, and 4.There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order. ... These types of problems are classified as NP-complete, and many examples that are algorithmically similar to encryption cracking can be seen at List of NP-complete problems.

For me this seems not accurate. For example, Graph-Isomorphism has this kind of attributes, but isn't NP-complete. Further more, I think that the most interesting part is whether BPP equals BQP or not. It is conjectured that factoring isn't in BPP, and this is the main reason for their power. sattath (talk)

Good catch. Changed! My edit may be a little heavy on the language. If you would, please look it over. Skippydo (talk) 07:52, 23 March 2008 (UTC)

[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)
  • I agree - this sounds like PR. sattath (talk)

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

Interesting, however, Random Algorithm+Error Correct=Random Algorithm. But to your point, a quantum computer can always run in classic mode and can therefore run non-random algorithms. Perhaps something to the effect "All quantum algorithms are randomized algorithms". Sill, I don't believe my suggestion addresses your concern. 125.14.79.216 16:28, 23 April 2007 (UTC)

How about "Quantum computers usually run randomized algorithms"? I gather there are deterministic quantum algorithms. User:Ben Standeven at 19:39, 9 May 2007 (UTC)

I went ahead and changed it to "Quantum computers only run probabilistic algorithms".125.14.79.216 03:04, 11 May 2007 (UTC)

I still don't believe this is true. For instance, the Deutsch-Jozsa algorithm returns a result with probability 1. Therefore, it is completely deterministic. This is perhaps a special case, as most other quantum algorithms require some element of randomness.Bjohnson00 04:26, 30 October 2007 (UTC)

All classical deterministic algorithms are classical probabilistic algorithms (P is a subset of BPP). The probability simply happens to be one. Skippydo 13:48, 30 October 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)
This isn't a forum, people. This has nothing to do with the article. Whether it is a "boondoggle" or not, it exists in some form and has an article. Please keep this discussion on how the article should be edited and keep opinions out. —Preceding unsigned comment added by 128.227.98.88 (talk) 16:37, 16 October 2007 (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

Sussurus' question was not addressed. The sentence says "asymptotically faster," when it should read "faster asymptotically," like kaz said but did not emphasize. I don't think Sussurus understands asymptotic analysis. —Preceding unsigned comment added by 131.118.72.137 (talk) 06:26, 15 November 2007 (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)

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?

Grover's algorithm is for an unstructured search. Shor's algorithm is for factoring an integer (rather order finding which is the heavy lifting in factoring). They answer different questions and cannot be compared. Shor's gives (logN)*3 running time. I assume by the quadratically better (logN)^1.5 you suggest that you wish to apply gover's on top of shor's, which cannot be done since grover's requires an Oracle. 125.14.79.216 16:44, 23 April 2007 (UTC)

Wrong. For shor's algorithm need time n2, while for grover algorithm 2n / 2 time, where n is number of qubits. —Preceding unsigned comment added by Weekwhom (talk • contribs) 05:22, 10 June 2008 (UTC)

[edit] Power of quantum computers

This comment is in response to the request for help with the Featured Article review:

The section Power of quantum computers is fairly convoluted and is asking for a clean-up. The main problem seems to be the lack of focus (or structure): it wanders into certain problems with known efficient quantum algorithms, than wanders away, comes back... The "author" cannot decide whether to hail quantum computers for being able to break cryptoalgorithms or reassuring the reader that not all is lost. I think that the best way to deal with it would be to adopt the traditional order of exposition:

1. Explain Feynmann's idea (quantum simulation on classical computers).

2. Give an informal explanation of Deutsch's problem and Grover algorithm.

3. Give a very brief but clean explanation of the difficulty of integer factorization and discrete logs for classical computers; then explain Shor's breakthrough. Avoid vague statements, like the one about 300 digit numbers unless they can be backed up in the text (seems unreasonable).

4. Summarize the current (with the disclaimer) gap between the power of classical and quantum computation. The implications for cybersecurity can be mentioned there, but without repetitions and too many qualifiers. Complexity-theoretic statements need to be cleaner. If there are a disagreements about inclusions between various complexity classes, this article is not the place to settle them.

5. Defer all discussion of 'why this works?' type to the corresponding articles or a separate section.

I hope this helps! Arcfrk 08:17, 10 April 2007 (UTC)

I agree with a lot of the above. This line is particularly a problem: "It seems plausible that it will always be possible to build classical computers that have more bits than the number of qubits in the largest quantum computer." How so? I understand the premise of the statement, but why can't quantum computers advance exponentially in relation to traditional machines? They certain could. There's no reference or explanation. That statement is an example of why that section is so convoluted.128.227.98.88 16:45, 16 October 2007 (UTC)

[edit] Quantic Noise And Quantum Computers

Couldn't quantum computers be made using classical electrical circuits with inputs with very high quantic noise? Whigh quantic noise would mean the input would be in a great number of possible states at the same time. This would then propagate to the remaining circuit, that could act as a filter that would select only the states that satisfied a given condition (SAT). This could be useful not only in cryptography but also protein folding and docking witch is basically a search for the lowest energy state.

[edit] Moved Futher Reading to Talk:Quantum_computer/Further_Reading

Please move anything back into the article you feel should not have been removed or place your comments on this action here. Skippydo 10:26, 27 July 2007 (UTC)

[edit] Reference misplaced

Ref 9 in the section "Quantum decoherence" is misplaced. Ref 9 does not discuss the increase of the number of qubits needed for fault tolerance. Rather, it questions the very possibility of fault tolerant quantum computation and presents a challenge for numerical verification of the proposed procedure for storing in memory just one qubit in the presence of realistic noise. (Karamzine 10:24, 10 August 2007 (UTC))

Section 6 on page 4 of the article you refer makes reference to the Shor code and Steane code. Specifically it mentions that 7 physical qubits are required for each theoretical qubit. It might be better to reference the Shor and/or Steane papers directly. Skippydo 13:50, 10 August 2007 (UTC)

[edit] Speed on the physical level

Okay, I understand the performance differences between quantum and classical computers on the theoretical level (Big-O notation): quantum computers probably have an advantage in integer factorization and possibly other problems as well. But what about the "actual" manipulation of data? Can quantum computers (or "can future quantum computers") actually flip and store (qu)bits at a much faster rate than classical computers? It seems to me like this should be the case, but I don't know. And if it is, wouldn't it not matter if quantum computers don't have an advantage over classical ones on the algorithm level, because they could emulate classical algorithms at a higher rate of speed? Or do I just have no idea what I'm talking about? Sloverlord 14:11, 29 August 2007 (UTC)

It depends on what you mean by faster. If you're talking asymptotically, then the answer is no.
If, by faster, you mean ticks of the clock, then do you have specific implementations in mind? Transistor classical computation vs ion trap quantum computing? Or vacuum tube classical vs NMRI quantum? What version of each processor? Skippydo 20:59, 31 August 2007 (UTC)
Are the various implementations so different in their capabilities that some would be faster than classical computers and others slower? Sloverlord 17:28, 6 September 2007 (UTC)

[edit] Probabilistic?

it is not true that quantum computers just solve probabilistically...they are actually deterministic. —Preceding unsigned comment added by 83.132.216.92 (talk) 00:24, 6 November 2007 (UTC)

[edit] pictures

any pictures of a real quantum computer?--200.73.179.203 03:29, 15 September 2007 (UTC)

[edit] QCs in fiction

Zegapain should be mentioned in the QCs in fiction section --David13579 23:32, 6 November 2007 (UTC)

Also, is there any point in the following line: "In Dan Brown's novel Digital Fortress, the NSA's cypher breaking computer TRANSLTR does NOT use quantum computing to break encryption keys of encrypted E-mails, it uses 3,000,000 silicon processors."? If it doesn't use quantum computing, why is it listed here? Calmac1991 (talk) 23:27, 27 March 2008 (UTC)

[edit] Can any of this be explained in layperson's terms?

I know this is probably asking the impossible, but can the general gist of this article be made accessible to someone without university level physics? Analogies might help. The example that comes to mind of such an analogy is that of heavy ball bearings sitting on a horizontal suspended rubber sheet to illustrate the curvature of space.

A walk-through example in very simple language might be good as well, for instance: What goes into a particular quantum logic gate, what happens there and what comes out of it?

As it is, I still haven't got the slightest clue why a set of 8 qubits should hold so much more information than 8 normal bits.

I hope this request doesn't seem thoughtless or rude. I am well aware of how difficult it is to make quantum physics intelligible to anyone, let alone non-physicists. Ireneshusband (talk) 22:07, 23 January 2008 (UTC)

You will not find any analogies to the world you think you live in. This cannot be explained using layman's terms. Anyone who claims to understand "what is really going on" does not.

On your specific questions, what "goes in" to a quantum logic gate depends on the implementation. A laser acting on a photon is an example of a quantum gate (not really gate like, is it?) 8 qubits cannot "hold" any more information than 8 classical bits. I'm assuming that "hold" means we can measure and recover the bits. Some dispute this meaning.

You aren't being thoughtless and rude and I hope I haven't been either. If you aren't disturbed and a little offended by quantum physics you haven't been paying attention. Skippydo (talk) 03:33, 29 January 2008 (UTC)

Well, I don't know that it's impossible to explain things in simpler language, but it's a challenge. It's especially difficult because there's a pretty technical debate going on between editors of the page. Didn't Einstein say something along the lines of "if you can't explain it to a child, you don't understand it"? Perhaps all physicists have failed Einstein's test on the matter of quantum mechanics. But we can always try to do better. Gnixon (talk) 16:50, 4 June 2008 (UTC)

[edit] Quantum computing without entanglement

http://arxiv.org/pdf/quant-ph/0511272v1

"Some cases have been found where even without entanglement, quantum computa- tion outperforms classical computation. Collins, Kim and Holton [15] solve the Deutsch- Jozsa (DJ) [5] problem without entanglement, but only for n = 2 bits, and prove that entanglement is required for any larger n; Braunstein and Pati [16] show that using pseudo-pure states, Grover’s search problem can be solved without entanglement for n ≤ 3 bits more efficiently than classically; Lloyd [17] suggests an entanglement-free implementation of Grover’s algorithm, but with exponential spatial complexity; Biham, Brassard, Kenigsberg and Mor [18] use a non-standard computation model, with a limitation on the number of allowed queries, to prove a tiny separation for any n in the context of Deutsch-Jozsa’s and Simon’s [6] problems (with mixed states); Meyer [19] notes that Bernstein-Vazirani algorithm [20, 21] requires no entanglement, yet uses only one oracle call, while the best classical algorithm requires n oracle calls."

Deutsch-Jozsa and Simon's algorithms don't have practical interest. And Bernstein-Vazirani algorithm probably also. But where it says about quantum computer? BTW, Deutsch-Jozsa algorithm can be solved effiecently on probabilistic computer. Simon algorithm have reasonably less advantages over classical computer than exponentional. So if entanglement decrease exponentionaly with number of qubits, then it's possible to do conclusion that Simon algorithm without entanglement also don't have any advantages over classical or probabilistic computer! Also key point can be, that for any quantum computing without entanglement need classical computer and usualy quantum computer taking more gates... —Preceding unsigned comment added by Weekwhom (talk • contribs) 08:17, 3 June 2008 (UTC)

In Reqursive Berstein-Vazirani algorithm need 2^{2^k} queries classicaly and 2k queries quantum mechanicaly (with entanglement). In Nonreqursive Berstein-Vazirani problem classicaly need n queries and quantum mechanicaly (with entanglement) 1 querie. It's possible that Bernstein-Vazirani algorithm without entanglement isn't faster than probabilistic computer.

"We investigated the advantage of quantum algorithms without entanglement over clas- sical algorithms, and showed a maximal entanglement-free subproblem of the Deutsch- Jozsa problem, which yields an O(1) to O(n) quantum advantage over the best exact classical algorithm. Due to this ban on entanglement, the exponential advantage of exact-quantum versus exact-classical is lost. For the Simon problem we showed that any non-trivial subproblem requires entanglement during the computation. Using a some- what different approach, we showed that this also holds for Grover’s algorithm. Further research on the role of entanglement in quantum information processing may illuminate some of the following questions: is there a restricted form of the Simon problem (or more generally of the hidden subgroup problem [22]), and a corresponding quantum algorithm that presents a quantum advantage without entanglement? Is there a subprob- lem larger than DJ⊗ and a corresponding algorithm (not the DJ algorithm) that solves it without entanglement, and yet has an advantage over any classical algorithm? Can there be a non-negligible advantage of QCWE over classical computation when separable mixed states are used? Can it be proved that exponential advantage of exact QCWE over classical-exact computation is impossible in oracle-based settings? Note that this is not known yet, even for the Deutsch-Jozsa problem, since there may be some other quantum procedure for which the QCWE advantage holds, and the subset is larger than F⊗DJ."

-It's unclear for simon algorithm about advantage without entanglement.


However, a sharp criticism has been proposed by Braunstein et al. that NMR experiments have not actually realized quantum algorithm because at each time step the state of the system can be described as a probabilistic ensemble of unentangled quantum states. On the other hand, some scientists believe that for a specific quantum algorithm the power of quantum computer derives from quantum superposition and parallelism, other than entanglement.

Quantum parallelism, I think, here means the randomly entangled qubits.
Stincky doubt about faster than classical Bernstein-Vazirani algorithm without entanglemen:

"We have described a classical optical scheme to implement the Bernstein-Vazirani algorithm. This scheme is entirely classical as we have used only ’classical qubits’ (based on the polarization states of light beams), and passive optical elements such as detectors, beam splitters, phase shifters and mirrors. The number of components needed to implement the algorithm increases linearly with the number of input beams. We have explicitly cloned the input and interfered it again with the part which undergoes the oracle unitary, in order to solve the Bernstein-Vazirani problem. This scheme does not require the implementation of any Hadamard gates. We have also shown through our interference arrangement that we can use the same oracle to compute f(x) for a given x. We believe that this analysis is a step in the direction where information processors based on interference of waves are analyzed in detail for their computation power. These systems seem to provide a model that is in-between the classical computation model based on bits and a fully quantum computer. The computational power is also likely to be in-between the two models (these issues will be discussed elsewhere)." http://arxiv.org/pdf/quant-ph/0605092

So where claims about faster quantum computation without entanglement? Where prove?


For Simon's algorithm need entanglement:

We conclude that the usage of the Simon algorithm for any subproblem of the Simon problem requires entanglement. However, an interesting open question in this context, is whether there is a restricted version of the problem solvable by some other quantum algorithm without entanglement, and achieves an advantage over the classical case. —Preceding unsigned comment added by Weekwhom (talk • contribs) 10:36, 3 June 2008 (UTC)

You yourself quote the following a maximal entanglement-free subproblem of the Deutsch- Jozsa problem, which yields an O(1) to O(n) quantum advantage over the best exact classical algorithm
Here's another: The quantum advantage that we have found is negligible (exponentially small). [7]
I assume this in response to this piece of the article:

Some computing architectures such as optical computers [3] may use classical superposition of electromagnetic waves. Without some specifically quantum mechanical resources such as entanglement, they have been shown to obtain no advantage over classical computers, entanglement is nessasary for exponential (or quadratic) advantage theoretically obtainable by quantum computer.

Would you rather:

Some computing architectures such as optical computers [3] may use classical superposition of electromagnetic waves. Without some specifically quantum mechanical resources such as entanglement, they have been shown to obtain only a negligible advantage over classical computers in a few cases, not the exponential (or quadratic) advantage theoretically obtainable by true quantum computers.

Skippydo (talk) 13:12, 3 June 2008 (UTC)


The quantum advantage that we have found is negligible (exponentially small). This is true for comparing determinist computer with quantum computer without entanglement, but probabilistic computer is faster or the same speed as quantum computer without entanglement in Deutsch-Jozsa problem. So your assumption is bad. P.S. Even probabilistic computer is faster than quantum computer with entanglement, becouse of error correction in quantum computer... —Preceding unsigned comment added by Weekwhom (talk • contribs) 15:01, 3 June 2008 (UTC)


About Grover algorithm without entanglement (and even without mixed entanglement): It is well known that this unary mapping comes at the cost of an exponential overhead in some physical resource. —Preceding unsigned comment added by Weekwhom (talk • contribs) 15:03, 3 June 2008 (UTC)

On your first comment, now, I'm not sure what you mean by faster. If you wish to compare actual runtime in second, you are comparing apples and oranges. When we compare algorithms, we generally speak asymptotically, in which case the quantum implementation enjoys a negligible advantage: Using a separable (that is, unentangled) state, we show that the Deutsch–Jozsa problem and the Simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic. [8] Skippydo (talk) 15:21, 3 June 2008 (UTC)

But when number of qubits increases in qunautum computer without entanglement increases advantages decreasing exponentionaly. And probably:

  • "The quantum advantage that we have found is negligible (exponentially small).

A much better advantage might be obtained by increasing � and investigating the separability of the speci;c states obtained throughout the unitary evolution of the algorithms.

  • The case of more than one query is left for future research." [9]
It is only for one querie. Don't you think that it is too unimportant? And it's scienciest I think comparing apples with oranges, becouse they don't quanting number of gates, etc, and that quantum computer must be controled with classical computer! Weekwhom


On your first point, you seems to be agreeing that quantum without entanglement is better than classical.
On your second point, I'm not sure what more than one query is meant to mean. We ask if a quantum computer enjoys an advantage over classical. The answer is yes. Do you not agree?
The mathematical formulation of a quantum computer is a Hillbert Space and Unary Transformations. There is no mention of classical computers. Likely, in an implementation some are need, but this is independent of the results.
Regardless, a quantum computer (with or without entanglement) can always run in classic mode. This means that a quantum computer is never inferior to a classical computer. Skippydo (talk) 15:18, 4 June 2008 (UTC)

After one querie in detusch-jozsa algorithm they both giving not good answer... But quantum computer without entanglement have a little bit bigger probability to give correct answer than probabilistic computer, I guess... But it's experimentaly wasn't tested, I think. And there still may be need more operations on quantum computer without entanglement than on probabilistic computer.

For probabilistic computer don't need stupid schemes, becouse answer still will be probabilistic, so for probabilistic computer need less gates than for quantum computer without entanglement and I think it can explain they missunderstanding that quantum computer without entanglement is faster than probabilistic computer (in deutsch-jozsa problem). —Preceding unsigned comment added by Weekwhom (talk • contribs) 05:33, 5 June 2008 (UTC)

The Deutsch-Josza algorithm is deterministic.
I don't understand what you mean by probabilistic computer need less gates than for quantum computer without entanglement. Consider a probabilistic classical algorithm and the Deutsch-Josza algorithm both being run on a quantum computer without entanglement. Asymptotically, the Deutsch-Josza algorithm wins. Skippydo (talk) 15:30, 5 June 2008 (UTC)

Consider a probabilistic classical algorithm and the Deutsch-Josza algorithm both being run on a quantum computer without entanglement. Asymptotically, the Deutsch-Josza algorithm wins. With more gates. Don't you see? Deutsch-Jozsa algorithm working with function, which taking some amount of gates, while for probabilistic computer don't need to care about any function it just randomly generates any bits and those bits is answer... OR may not... Sory, I spent somthing... But advantages of quantum computer is only after one querie so it's don't matter so much... And for example enetanglement are good only with photons and photons taking many space... But possible also that deutsch-jozsa algorithm requiring more operations than in probabilistic computer solving this problem case. I am only familiar with Deutsch-Jozsa algorithm with entanglement and can tell you that Deutsch-Jozsa algorithm with entanglement isn't faster than classical computer in the same problem? Why? There is very strong asumption for this. First of all. Classical computer don't using aditional Hadamard gates! Also for classical computer don't need error correction, which increasing number of gates up to 1000 times (according to some optimistic theoretical expectations of possibility of quantum errors correction). But probabilistic computer can give you correct answer after n queries and fail probability is 1 / 2n, while for quantum algorithm need only 1 querie (and more gates for error correction and hadamard gates) with certainty. But what is mean 100%? It means, that if error correction don't have fail probability, but it actualy have theoreticaly about 1 / 215, thus after 15 trys probabilistic computer will solve deutsch jozsa problem as succesfuly as quantum computer with entanglement. After two queries of quantum computer error correction fail probability is 1 / 230, thus need 30 queries of probabilistic computer to get the same probability. But quantum computer cirquit is more than 15 times complex and thus everything is equal and even probabilistic computer doing better. Thus Deutsch jozsa algorithm with entanglement and error correction isn't faster than probabilistic computer. So I am now searching weak point of Deutsch-Jozsa algorithm without entanglement over probabilistic computer, but since I don't understand Deutsch algorithm without entanglement, then is up to you... But I am thinking, thut deutsch-jozsa algorithm quantum computer without entanglement cirquit may be more complex than probabilistic computer cirquit and then exponentionaly small advantage don't playing any role and they are equal. And by the way, Deutsch-Jozsa algorithm don't have practical tasks... —Preceding unsigned comment added by Weekwhom (talk • contribs) 18:04, 5 June 2008 (UTC)

Gate complexity is polynomial (in fact linear) with respect to the DJ algorithm. Gate complexity doesn't effect speed. In the mathematical model of quantum computing we are assuming, no error correction is required. Skippydo (talk) 18:47, 5 June 2008 (UTC)
But required more gates, becouse Deutsch-Jozsa algorithm with entanglement using about 2n hadamard gates, where n is number of qubits and all over size of cirquit is the same. Hadamrd gate is prety dificult operation I guess, so possible that even in mathematical model Deutsch -Jozsa algorithm isn't faster than probabilistic computer (becouse everything is the same, except that qunatum computer using aditional 2n hadamard gates). Sciencists seems don't counting hadamrd gates into quantum computer complexity or if I am wrong, then hadamrd gates are very simple and negligable operation, which can be ignored - I am not sure about that... But I just can say, that roughly for Deutsch jozsa algorithm need about <n/2 C-NOT gates and about <n/2 NOT gates. But again, quantum CNOT gate can be more complex than classical XOR gate and quantum NOT gate can be more complex than classical NOT gate. There can be that sciecists comparing apples with oranges and then getting they polinomial speedup over probabilistic computer and exponentional speedup over classical computer (but not always...). —Preceding unsigned comment added by Weekwhom (talk • contribs) 05:40, 6 June 2008 (UTC)


Some cases have been found where even without entanglement, quantum computation outperforms classical computation. Collins, Kim and Holton solve the Deutsch-Jozsa (DJ) problem without entanglement, but only for n = 2 bits, and prove that entanglement is required for any larger n;

You see, Deutsch-Jozsa algorithm is faster only for case when number of qubits is 2 and only after one querie! Isn't it don't looks very not important? —Preceding unsigned comment added by Weekwhom (talk • contribs) 05:47, 6 June 2008 (UTC)
From the same paper seems, that Deutsch algorithm without entanglement using Hadamard gates and combining it with exponentionaly small advatages and with fact that probabilistic (or classical) computer don't using additional 3 Hadamard gates, there possible to made conclusion, that Deutsch algorithm without entanglement isn't faster than probabilistic or classical computer, becouse have 3 gates more than probabilistic computer. This exponentionaly small advatnage 1 / 22 = 1 / 4 = 0.25 can compensate fact, that classical computer don't using hadamrd gates! —Preceding unsigned comment added by Weekwhom (talk • contribs) 05:56, 6 June 2008 (UTC)

I think you are right in mathematical model quantum computer with entanglement with Deutsch-Jozsa algorithm is faster than probabilistic computer, becouse even if deutsch-Jozsa algorithm using 4 times more gates than probabilistic computer or even 100 times more gates it still don't matter, becouse probabilistic computer will fail with probability 1 / 2100 = 10 − 30, while quantum computer fail probability is 0. But fail probability 1 / 2100 is so small that faster come end of univerese and everything will explode and thus quantum computer also and thus will not be advantages of quantum computer... Weekwhom

Notice that it's query complexity we compare in the Deutsch-Jozsa algorithm, fixing probability and time. From the paper you cite: Note also that here the quantum-to-classical gap in the exact case diminishes from O(2^n ):O(1) to O(n):O(1). This is the price we pay for not using entanglement. Constrasting this with what you have quoted, I'm a little confused Skippydo (talk) 12:59, 6 June 2008 (UTC)

I actualy don't understand understand this qoute very good "...diminishes from O(2n):O(1) to O(n):O(1). This is the price we pay for not using entanglement."; According to my understanding quantum computer (with entanglement) is only sometimes exponentionaly faster and sometimes polinomialy, but there probably talking about exponentional speedup in quantum computer and polinomial inDeutsch-Jozsa algorithm without entanglement, but I am also cofused, that in over place there says, that entanglement is required for more than 2 qubits in Deutsch-jozsa algorithm without entanglement. There is some don't maching in those papers, one says that advantage is exponentionaly small and after one querie over don't saying nothing about queries... And I don't find more papers than those two, maybe those papers are rubish? Sometimes on arxiv.org there is wrong papers. —Preceding unsigned comment added by Weekwhom (talk • contribs) 17:45, 6 June 2008 (UTC)