“Can you give me a simple, concrete explanation of how quantum computers work?”
I’ve been asked this question a lot. I worked on quantum computing full time for 12 years, wrote 60 or so papers, and co-authored the standard text
It turns out, though, that there is a satisfying answer to the question, which anyone can understand if they’re willing to spend some time concentrating hard.
To understand the answer, let’s back up and think first about why big media outlets like the New York Times and the Economist regularly run stories about quantum computers.
The reason is that quantum computer scientists believe quantum computers can solve problems that are intractable for conventional computers. That is, it’s not that quantum computers are like regular computers, but smaller and faster. Rather, quantum computers work according to principles entirely different than conventional computers, and using those principles can solve problems whose solution will never be feasible on a conventional computer.
In everyday life, all our experience is with objects which can be directly simulated by a conventional computer. We don’t usually think about this fact, but movie-makers rely on it, and we take it for granted – special effects are basically just rough computer simulations of events that would be more expensive for the movie makers to create in real life than they are to simulate inside a computer. Much more detailed simulations are used by companies like Boeing to test designs for their latest aircraft, and by Intel to test designs for their latest chips. Everything you’ve ever seen or done in your life – driving a car, walking in the park, cooking a meal – all these actions can be directly simulated using a conventional computer.
Because of this, when we think in concrete terms we invariably think about things that can be directly simulated on a conventional computer.
Now, imagine for the sake of argument that I could give you a simple, concrete explanation of how quantum computers work. If that explanation were truly correct, then it would mean we could use conventional computers to simulate all the elements in a quantum computer, giving us a way to solve those supposedly intractable problems I mentioned earlier.
Of course, this is absurd! What’s really going on is that no simple concrete explanation of quantum computers is possible. Rather, there is an intrinsic quantum gap between how quantum computers work, and our ability to explain them in simple concrete terms. This quantum gap is what made it hard for me to answer people’s requests for a concrete explanation. The right answer to such requests is that quantum computers cannot be explained in simple concrete terms; if they could be, quantum computers could be directly simulated on conventional computers, and quantum computing would offer no advantage over such computers. In fact, what is truly interesting about quantum computers is understanding the nature of this gap between our ability to give a simple concrete explanation and what’s really going on.
This account of quantum computers is distinctly at odds with the account that appears most often in the mainstream media. In that account, quantum computers work by exploiting what is called “quantum parallelism”. The idea is that a quantum computer can simultaneously explore many possible solutions to a problem. Implicitly, such accounts promise that it’s then possible to pick out the correct solution to the problem, and that it’s this which makes quantum computers tick.
Quantum parallelism is an appealing story, but it’s misleading. The problem comes in the second part of the story: picking out the correct solution. Most of the time this turns out to be impossible. This isn’t just my opinion, in some cases you can mathematically prove it’s impossible. In fact, the problem of figuring out how to extract the solution, which is glossed over in mainstream accounts, is really the key problem. It’s here that the quantum gap lies, and glossing over it does nothing to promote genuine understanding.
None of my discussion to now actually explains how quantum computers work. But it’s a good first step to understanding, for it prepares you to expect a less concrete explanation of quantum computers than you might at first have hoped for. I won’t give a full description here, but I will sketch what’s going on, and give you some suggestions for further reading.
Quantum computers are built from “quantum bits”, or “qubits” [1], which are the quantum analogue of the bits which make up conventional computers. Here’s a magnified picture of a baby quantum computer made up of three Beryllium atoms, which are used to store three qubits:
(credit to the NIST trapped ions group)The atoms are held in place using an atom trap, which you can’t see because it’s out of frame, but which surrounds the atoms, holding them suspended in place using electric and magnetic fields, similar to the way magnets can be used to levitate larger objects in the air.
The atoms in the picture are about three micrometers apart, which means that if you laid a million end to end, they wouldn’t quite span the length of a living room. Very fine human hair is about 20 micrometers in diameter – it’d pretty much cover the width of this photo.
The atoms themselves are about a thousand times smaller than the spacing between the atoms. They look a lot bigger in the picture, and the reason is interesting. Although the atoms are very small, the way the picture was created was by shining laser light on the atoms to light them up, and then taking a photograph. The particles making up the laser light are much bigger than the atoms, which makes the picture come out all blurry; the photo above is basically a very blurry photograph of the atoms, which is why they look so much bigger than they really are.
I called this a baby quantum computer because it has only three qubits, but in fact it’s pretty close to the state of the art. It’s hard to build quantum computers, and adding extra qubits turns out to be tricky. Exactly who holds the record for the most qubits depends on who you ask, because different people have different ideas about what standards need to be met to qualify as a genuine quantum computer. The current consensus for the record is about 5-10 qubits.
Okay, a minor alert is in order. I’ve tried to keep this essay as free from mathematics as possible, but the rest of the essay will use a little high-school mathematics. If this is the kind of thing that puts you off, do not be alarmed! You should be able to get the gist even if you skip over the mathematical bits.
How should we describe what’s inside a quantum computer? We can give a bare-bones description of a conventional computer by listing out the state of all its internal components. For example, its memory might contains the bits 0,0,1,0,1,1, and so on. It turns out that a quantum computer can also be described using a list of numbers, although how this is done is quite different. If our quantum computer has n qubits (in the example pictured above n = 3), then it turns out that the right way to describe the quantum computer is using a list of 2n numbers. It’s helpful to give these numbers labels: the first is s1, the second s2, and so on, so the entire list is:
What are these numbers, and how are they related to the n qubits in our quantum computer? This is a reasonable question – in fact, it’s an excellent question! Unfortunately, the relationship is somewhat indirect. For that reason, I’m not going to describe it in detail here, although you can get a better picture from some of the further reading I describe below. For us, the thing to take away is that describing n qubits requires 2n numbers.
One result of this is that the amount of information needed to describe the qubits gets big really quickly. More than a million numbers are needed to describe a 20-qubit quantum computer! The contrast with conventional computers is striking – a conventional 20-bit computer needs only 20 numbers to describe it. The reason is that each added qubit doubles the amount of information needed to describe the quantum computer [2]. The moral is that quantum computers get complex far more quickly than conventional computers as the number of components rises.
The way a quantum computer works is that quantum gates are applied to the qubits making up the quantum computer. This is a fancy way of saying that we do things to the qubits. The exact details vary quite a bit in different quantum computer designs. In the example I showed above, it basically involves manipulating the atoms by shining laser light on them. Quantum gates usually involve manipulating just one or two qubits at a time; some quantum computer designs involve more at the same time, but that’s a luxury, it’s not actually necessary. A quantum computation is just a sequence of these quantum gates done in a particular order. This sequence is called a quantum algorithm; it plays the same role as a program for a conventional computer.
The effect of a quantum gate is to change the description s1, s2,… of the quantum computer. Let me show you a specific example to make this a bit more concrete. There’s a particular type of quantum gate called a Hadamard gate. This type of gate affects just one qubit. If we apply a Hadamard gate to the first qubit in a quantum computer, the effect is to produce a new description for the quantum computer with numbers t1, t2,… given by
t1 = (s1+s2n/2+1)/√ 2
t2 = (s2+s2n/2+2)/√ 2,
t3 = (s3+s2n/2+3)/√ 2,
and so on, down through all 2n different numbers in the description. The details aren’t important, the salient point is that even though we’ve manipulated just one qubit, the way we describe the quantum computer changes in an extremely complicated way. It’s bizarre: by manipulating just a single physical object, we reshuffle and recombine the entire list of 2n numbers!
It’s this reshuffling and recombination of all 2n numbers that is the heart of the matter. Imagine we were trying to simulate what’s going on inside the quantum computer using a conventional computer. The obvious way to do this is to track the way the numbers s1, s2,… change as the quantum computation progresses. The problem with doing this is that even a single quantum gate can involve changes to all 2n different numbers. Even when n is quite modest, 2n can be enormous. For example, when n = 300, 2n is larger than the number of atoms in the Universe. It’s just not feasible to track this many numbers on a conventional computer.
You should now be getting a feeling for why quantum computer scientists believe it is infeasible for a conventional computer to simulate a quantum computer. What’s really clever, and not so obvious, is that we can turn this around, and use the quantum manipulations of all these exponentially many numbers to solve interesting computational problems.
I won’t try to tell that story here. But if you’re interested in learning more, here’s some reading you may find worthwhile.
In an earlier essay I explain why conventional ways of thinking simply cannot give a complete description of the world, and why quantum mechanics is necessary. Going a little further, an excellent lay introduction to quantum mechanics is Richard Feynman’s QED: The Strange Theory of Light and Matter
Finally, if you’ve enjoyed this essay, you may enjoy some of my other essays, or perhaps like to subscribe to my blog. Thanks for reading!
Acknowledgements
Thanks to Jen Dodd and Kate Nielsen for providing feedback that greatly improved early drafts of this essay.
About the author
Michael Nielsen is a writer living near Toronto, and working on a book about The Future of Science. If you’d like to be notified when the book is available, please send a blank email to the.future.of.science@gmail.com with the subject “subscribe book”. You’ll be emailed to let you know when the book is to be published; your email address will not be used for any other purpose.
Footnotes
[1] Ben Schumacher, who coined the term “qubit”, runs an occasional blog.
[2] Motivated by this observation, in my PhD thesis I posed a tongue-in-cheek quantum analogue of Moore’s Law: to keep pace with conventional computers, quantum computers need only add a single qubit every two years. So far, things are neck and neck.
i get your point, but on the other hand there are quantum computing APIs for perl 😉
Raoul – there are certainly ways of simulating a quantum computer on a conventional computer. But all the ways known are incredibly inefficient, i.e., have exponential overhead. There is no simple, concrete model of a quantum computer that allows a direct simulation.
Haskell also has a modal for simulating quantum computing. Sure, its inefficient, but pretty nifty.
“The particles making up the laser light are much bigger than the atoms”… uh, what?
Dear Dr.Nielsen,
I am grad student who has been pursuing QC for the last 2 yrs and i regularly your ur textbook!
I found this post very relevant because i always have trouble explaining my friends in simple terms about my QC research 🙂
I really liked your idea of the quantum gap!
I have a personal question for you.
I am doing my PhD in QC and i am worried about the future of QC.Will it ever become a mainstream field or will my PhD go waste?So far we are very far from a scalable qubit system.
I would be thankful to you if you could express your opinion on the future of this exciting field.
Confused – I didn’t put that very well. The basic point is that the wavelength of the laser light is about one tenth of a micrometer (I forget exactly what it was for this experiment, but it was in roughly that range). While that’s pretty small, it’s still huge when compared with the atoms. Hope that clears things up!
Parasa – I’m not sure what you mean by a mainstream field. To me, quantum computing already looks pretty mainstream.
“For example, when n = 300, 2n is larger than the number of atoms in the Universe.”
Well, the record so far is n<=10 you say. A computer is fully capable to simulate 1024 variables. It still has exponential complexity, but why shouldn’t it be possible to write a slow, limited, simple, concrete simulator?
Andreas – yes, a slow simulation is possible, in terms of those 2^n variables. It’s not what most people would regard as a concrete simulation, though, since those 2^n variables aren’t related to the physical picture in a simple, concrete fashion.
Michael, how can there be any well-defined performance gap between classical computers and quantum computers, when classical computers *are* quantum computers?
Isn’t it better-posed—both physically and mathematically—to distinguish between high-noise computers (that are designed to correct only bit-flip errors) versus low-noise computers (that are designed to correct bit-flip errors *and* phase errors)?
If noisy computers are inherently easier to simulate—as seems reasonable on physical grounds—this would help us understand why progress in simulating noisy quantum systems (including especially low-temperature systems) has far outstripped even Moore’s Law, for the past several decades.
Is there any obvious end in sight, to this wholly algorithm-based progress in simulation capability?
QIT articles continue to appear that assert “Digital simulations of large scale quantum many-body Hamiltonians are essentially hopeless on classical computers.”
But when it comes to noisy and low-temperature systems, the available evidence indicates that the opposite is true, doesn’t it?
The quantum chemists surely seem to think so: the August 8, 2008 theme issue of Science is dedicated to this proposition. 🙂
No problem with the mathematics and effectiveness of low dimensional Hilbert space models used in quantum computing/information. Don’t wanna do mathematics about experiments any other way. Still, these low dimensional models are generally held to be subspaces of an infinite dimensional quantum field model. I argue in various papers that such models can be matched by classical random fields, provided the whole experimental apparatus is described as a system of interacting random fields instead of as a system of putatively isolated particles/systems. Isolated particles are as ephemeral and emergent in random field models as they are in quantum field models.
A random field model is a step beyond a classical analogue computer, with, I surmise, the same computing power as that of quantum fields. This does not make quantum computing much easier to explain to your grandmother right now, but in the future it might. In any case, it allows a different reconciliation of quantum and classical than previously available accounts.
I laud your noble effort at trying to convey an answer that is both correct and understandable—not an easy task!
Personally, I’m not too keen on starting with the premise that our classical computing minds can’t grasp quantum computing, mainly because I don’t believe it. If it were true, we wouldn’t be able to have a mathematical model of quantum mechanics! Certainly great minds like Bohr and Feynman are associated with famous quotes about quantum mechanics not being understandable, but I don’t think they ever meant that the task is impossible.
I’m also not too keen on this 2^n versus n comparison between quantum and deterministic classical computers as a method for explaining the difference. I think a better way to make the comparison is to introduce in a conversational way the notion of a probabilistic computer, which also can take on 2^n configurations, and a classical wave computer, which can compute with minus signs but only over n configurations. A large part (all?) of the power of quantum computing comes from its ability to have 2^n configurations *and* minus signs at the same time. Neither by itself offers computational speedups, but put them together and you essentially get quantum computing (which itself may or may not be more computationally powerful). This approach sidesteps the differences between Bayes’ rule for probabilistic computers and the Born rule for quantum computers, which may be equally as important as the cluster-state model of quantum computing highlights.
Andrew: “Personally, I’m not too keen on starting with the premise that our classical computing minds can’t grasp quantum computing, mainly because I don’t believe it.”
Neither am I, which is why I didn’t write it. I merely said that a direct concrete explanation isn’t possible. If it were, you could describe an n-qubit quantum computer using an amount of information proportional to n.
Andrew: “I’m also not too keen on this 2^n versus n comparison between quantum and deterministic classical computers as a method for explaining the difference.”
My purpose in the second part of the essay was to do two things: (1) give a glimpse of how we describing quantum computers; and (2) give some understanding of why we have so much trouble simulating quantum computers on conventional computers.
I’m not trying in that part to explain the entire gap between conventional and quantum computing, which is a more ambitious goal, and which is what you’re trying to get at.
Dear Mr. Nielsen,
Is the statement ‘Quantum information theory is generalisation of classical Information theory’ scientific fact or just something what is believed in and needs a proof ? If it is proven, which scientific method is used (mathematical, physical or their combination) ?
With highest respect,
Alexander
Will the Introductory lecture notes on quantum information and computation be made available again.
Sam Kohn
Sam Kohn – The links to the lectures should now be fixed.
Thanks for these “simple” explanations. Although I have an engineering background I can’t easily manage the mathematicae behind QC and it seems to me that there might be huge opportunities applying QC to business information systems.
I am a business consultant and usually deal with dataming problems and stochastic rules for managing complex business processes. Any advance on these fields based on QC? I can roughly imagine “unimaginable” possibilities: management of huge amounts of unstructured data, simulation of thousands of business scenarios with just a mouse-click…
Further explanations, blogs or papers with regard to these issues would be very welcome. Thanks in advance!
Pau Velando – I don’t know of any application of quantum computing yet in this vein (e.g., data mining).
I’m reminded of Dougla Adam’s description of the discovery of the inifinite improbability drive: “The Infinite Improbability Drive is a wonderful new method of crossing vast intersteller distances in a mere nothingth of a second without all that tedious mucking about in hyperspace.It was discovered by a lucky chance, and then developed into a governable form of propulsion by the Galactic Government’s research team on Damogran.This, briefly, is the story of its discovery.The principle of generating small amounts of finite improbability by simply hooking the logic circuits of a Bambleweeny 57 sub-meson Brain to an atomic vector plotter suspended in a strong Brownian Motion producer (say a nice hot cup of tea) were of course well understood – and such generators were often used to break the ice at parties by making all the molicules in the hostess’s undergarments leap simultaneously one foot to the left, in accordance with the Theory of Indeterminacy.Many respectable physicists said that they weren’t going to stand for this – partly because it was a debasement of science, but mostly because they didn’t get invited to those sort of parties.Another thing they couldn’t stand was the perpetual failure they encountered in trying to construct a machine which could generate the infinite improbability field needed to flip a spaceship across the mind-paralysing distances between the furthest stars, and in the end they grumpily announced that such a machine was virtually imposssible.Then, one day, a student who had been left to sweep up the lab after a particulary unsuccessful party found himself reasoning this way:If, he thought to himself, such amachine is a virtual impossibility, then it must logically be a finite improbability. So all I have to do in order to make one, is to work out exactly how improbable it is, feed that figure into the finite improbability generator, give it a fresh cup of really hot tea … and turn it on!He did this, and was rather startled to discover that he had managed to create the long sought after golden Infinite Improbability generater out of thin air.It startled him even more when just after he was awarded the Galactic Institute’s Prize for Extreme Cleverness he got lynced by a rampaging mob of respectable physicists who had finally realized that the one thing they really couldn’t stand was a smartass.”
I am thinking about “universality”…
Thay said in 2008 that there exist more than 12 ways to use qubits in quantum computing.
http://mags.acm.org/communications/200807/?pg=14
But just recenty they announced the first “universal” quantum processor that is cabable to perform whatever computing operation. Before that it was possible to operate only with some algorithms by using qubits.
http://physicsworld.com/cws/article/news/40949
May I ask how do you prefer the QM interpretation, Copenhagen or Everett?
May I ask do quantum games reflect the process of evoultion ?
Dear Prof.Nielsen,
Thanks a lot for your beutiful book.
Please let me know do you have the solution for the problem of your book “Quantum information and quantum computation”?
In case you have I would very appreciate if you possibly let me know how can I get it.
Sincerely your,
Fasihi
Do You know any application of quantum games or quantum random walks in finance ?
Great post, and well written. I was looking for information on quantum computers on the net, and this article made things a bit clearer, and explained things I haven’t found explained in the other articles or videos I found. Read some of your other posts, and they were interesting as well.
how can i get an quantum simulator?
for example for simulation TSP in an quantum way.
For example, when n = 300, 2n is larger than the number of atoms in the Universe
You really need a superscript tag or ^ here.
Thanks – turns out the superscript and subscript tags were there, but a bug in my WordPress theme meant they did not display. I’ve fixed the bug.
Would a decent comparison be a vinyl record that uses natural mechanics and has no numerical values of sound compared to a cd with a digital, numerical representation of what used to be a smooth continuous sound wave? You can get pretty close with a cd, and using a higher bit and sample rate (aka, stronger computer) gives you a more refined version of the soundwave, but you can still zoom in and see jagged edges to the wave no matter how refined you go, whereas the analogue piece of vinyl is a pure wave which really represents what actually happened (or will happen) …
Still don’t know how you would actually apply the quantum computer to a real life situation, it seems to be a tool to measure itself, like a magic 8 ball
Dear Dr. Nielsen,
Thank ou for your courageous attempt to explain what a QC is like. I -however- got stuck with the following, and this nags me too much to be able to follow the rest:
You state a 20-bit conventional ‘computer’ can be described in 20 numbers, and a 20-qubit QC needs 2^20 numbers
….but that is not right, is it? Even if the conventional computer were to consist of nothing more than 20 flipflops (which it doesn’t, it consists of millions of them), even then the group of 20 flipflops can be in any of 2^20 states. Of course these 2^20th states could each be given a number, and to do that one -indeed- needs 20 binary digits only.
My point is: I do not get why this is different in a QC with -say- 20 of them berylium atoms? It would imply a single of these atoms can have two states, and if you bring two of them together the pair could have more than 4 states, where the proximity triggers the emergence of the extra ones.
If I try to follow your description, we would need 2^2=4 numbers to describe the state of two atoms….are those numbers not 00, 01, 10 and 11, then?, or do you mean to say that each Qubit in a group of 1 can have 2 states, and each qubit in a group can have 4 individual states, so that the group of two can have not 2^2 but 4^2 states??
If the latter is what you mean, an QC -unlike a binary cc, has a duble exponential growth of states: a n flipflop binary CC can be in any of 2^n states, and an n-qubit QC can be in any of (2^n)n states.
Anyhow..I’m confused, as may be obvious from the above. Would love your clarification, thanks in advance.
Ivo.
Further to the above, I spotted a few typo’s that make things confusing, here is the text improved:
___________
Thank you for your courageous attempt to explain what a QC is like. I -however- got stuck with the following, and this nags me too much to be able to follow the rest:
You state a 20-bit conventional ‘computer’ can be described in 20 numbers, and a 20-qubit QC needs 2^20 numbers to be fully described.
….but that is not right, is it? Even if the conventional (binary) computer were to consist of nothing more than 20 flipflops (which it doesn’t, it consists of millions of them), even then the group of 20 flipflops can be in any of 2^20 states. Of course these 2^20th states could each be given a number, and to do that one -indeed- needs 20 binary digits only.
My point is: I do not get why this is different in a QC with -say- 20 of them berylium atoms? It would imply a single of these atoms can have two states, and if you bring two of them together the pair could have more than 4 states, where the proximity triggers the emergence of the extra ones, correct?
If I try to follow your description, we would need 2^2=4 numbers to describe the state of two atoms….are those numbers not 00, 01, 10 and 11, then? Or do you mean to say that a single Qubit (a qubit in a group of 1 can have 2 states), and each qubit in a group of 2 can have 4 individual states, so that the group of two can have not 2^2 but 4^2 states??
If the latter is what you mean, an QC -unlike a binary cc, has a double exponential growth of states: an n-flipflop binary CC can be in any of 2^n states, and an n-qubit QC can then be in any of (2^n)^n states.
Anyhow..I’m confused, as may be obvious from the above. Would love your clarification, thanks in advance.
Ivo.
Thanks Dr Nielson I think I understand more that I did before reading.
Just letting you know the link in the credit of the image of the atoms is broken, or the resource has been moved.
http://www.nist.gov/public_affairs/quantum/how_to_entangle_ions.html
Thanks
@Eacsoft: Glad you found it useful. Thanks to let me know the credit link is broken. They seem to have taken it off their site entirely, so I replaced the link with a generic credit link.
Sir,
I have finished seond year of my B.Sc. Physics. I have studied basics in quantum mechanics. I am working on Quantum Computation & Quantum Information for my summer project for two months. But I’m unable to find a topic. Please atleast suggest me a way to find the right topic. Thanks in advance.
Interesting attempt at an explanation. However, here is a small curve ball to consider. How would your explanation of the inexplicable look if someone proved (mathematically) that quantum devices evolve according to a scheme of mathematics that is a special case of classical mechanics?
To put this differently.
What would happen to this field if we found out that abstract classical computers could simulate abstract quantum computers of equivalent phase space dimension?
If that were so, then quantum computers would be a special case of classical computers.
Hmmm… Let is hope nobody ever proves any mathematical result like that!
@Kingsley – That’s why I put the caveat “believe” in the sentence “quantum computer scientists believe quantum computers can solve problems that are intractable for conventional computers”. The rest of the essay is conditional on that being true.
Personally, I think this is likely to be true, but perhaps not quite as likely as many quantum computer scientists. Indeed, in some sense I even hope it’s true: it’d be a remarkable breakthrough in our understanding of quantum mechanics!
Michael,
The most intuitive QFT and quantum-computing model is Macroscopic Phonons. Suddenly one sees quantum computing processes all around us.
For example, consider a child’s kite as a basic quantum-computer suited to solve its flight control problem. Consistent with QFT and quantum computing theory, one finds phononic qubit “cells” in the kite stick and membrane field: one pair encodes yaw, another pitch, and so on. The wind itself is a quantum phonon qubit (or packet of qubits). The kitestring is a quibit cell. As these qubits interact as a computer, the kite flies. Its a “quantum robot” 🙂
On the other hand, a kite cab be designed with no embodied quantum-computed “inherent stabilities”, but instead depend on a complex digital sensor/microcontroller/actuator “classical” control system, which adds prohibitive cost and mass.
The utter elegance of the embodied phonon-based quantum computation is quite apparent.
Please copy me by email if you have a specific reply to this conjecture.
Mr Michael Nielsen
I finished my post graduate in Computer Science.
I want to do Phd in Quantum Computing.
Can i do?
Please give your advise.
What type of knowledge i need for QC.
Dear Dr.Nielsen,
I’ve read and read your explanation of QC, and still i can’t imagine what QC is.
I have no history in engineering/math/science, but I am an avid fan and bystander of science and technology.
So I have some really really stupid questions for you.
1. What would a QC look like? what kind of user interface would it have?
2. What would we use a QC for in day to day life? Or is it rather an instrument for scientific research?
I have warned you about the ignorance of my questions 🙂
But I would be very grateful for any thoughts or answers.
Thank you in Advance,
Kind regards,
MvH
It is well-known that Quantum Computer can speedup the algorithms exponentially, e.g. Shor’s Algorithm. But, in some cases it can’t do so, e.g. Grover’s Algorithm for which it can achieve sqrt(N) speedup at Best.
Can there be algorithms where Classical (conventional) Computer can do better than Quantum Computer?
I am confused by an article claiming such speedup. The link to the article is
http://vixra.org/pdf/1306.0193v2.pdf
Please guide in this respect.
DPM
Any classical algorithm can be converted to run on a quantum computer with only a small change in complexity. But the classical computer might (potentially) have faster gates, so it could potentially benefit that way.
That article doesn’t look interesting to me.
I think you are right. The article is not interesting because the suggested method of sorting consisting of preparing state vector for scrambled list and reading this vector from left to right to get back the sorted list though very impressive is not better because of the “memory issue”.
Suppose we want to sort even some 10000 numbers only, still if the sizes of the numbers have very wide range, i.e. if they belong in the range (0, 2^32) then Bubble sort or some other equivalent sort will be much better way to get the job done in practice.
DPM
Is it possible to use entanglement for information transfer with speed faster than that of light?
What is your comment on the paper at: http://vixra.org/pdf/1402.0142v1.pdf ?
Sir,
You spoke about Quantum circuits in this essay. In order to approximate an arbitrary Quantum gate using the universal set of gates, is there any general algorithm to do that? Because I wondered how you realized the Toffoli gate using the universal set of gates in your book.
Because I’ve found a method to achieve any permuatation of a 8×8 unit matrix just by using CNOT and TOFFOLI gates. I don’t know anything about the efficiency or if it already exists or not. Just found it with little observation while working out the exercise of your book.
Also one more question: As long as the qubits are not in the non-decomposable states such as Bell states, can’t they be represented as n 2×2 matrices? Whenever say the amplitude of state |u> is needed it takes utmost n multiplications in this case to retain it. [Of course, it takes 2^n steps to retain the complete state of the system]. It looks a little efficient because in order to manipulate a single qubit, we no longer need to update 2^n numbers, but simply 2 numbers in case of single qubit gates, or 4 numbers in case of 2-qubit gates which form a universal set.