Does anyone know what "Quantum Computing" is? [closed]

Question

In physics, its the ability for particles to exist in multiple/parallel dynamic states at a particular point in time. In computing, would it be the ability of a data bit to equal 1 or 0 at the same time, a third value like NULL[unknown] or multiple values?.. How can this technology be applied to: computer processors, programming, security, etc.?.. Has anyone built a practical quantum computer or developed a quantum programming language where, for example, the program code dynamically changes or is autonomous?

Holbert

I think that wikipedia/quantum_computer article is pretty much there. – Otto

maybe someday a "quantum internet" would have the ability to teleport physical objects from one place to another? – Muir

@Frank: well, who knows, but that's a completely separate issue from quantum computing. – Randellrandene

Also, here's a similar question on SU that I answered recently (I could give the same answer here but I figure a link is more efficient): superuser.com/questions/156705/what-is-a-quantum-processor – Randellrandene

You also might want to look at this. quantiki.org – Ube

Perhaps a "quantum internet" would be the answer to ensuring privacy!.. banks have been using quantum encryption for secure communication. – Muir

Quantum computation, quantum encryption, and other consequences of quantum physics are all entirely different topics. Best not to confuse them. – Whimsy

When are "quantum computers" going to be commercially available?.. I'm sure the government already has them!.. They're always atleast 5 to 10 years ahead of commercial technology. – Muir

Are there any new developments/progress related to this topic? – Muir

I can only say: "Try to read, understand and absorb this article on Ars" arstechnica.com/science/guides/2010/01/… – Dafna

Regarding what can be solved with quantum computers: A quantum computer would break current asymmetric encryption schemes. It is a common misconception, that quantum computers can solve most optimization problems. They cannot. See This article for more details what can be solved using quantum computers and what cannot. – Blaubok

Answer 1

I have done research in quantum computing, and here is what I hope is an informed answer.

It is often said that qubits as you see them in a quantum computer can exist in a "superposition" of 0 and 1. This is true, but in a more subtle way than you might first guess. Even with a classical computer with randomness, a bit can exist in a superposition of 0 and 1, in the sense that it is 0 with some probability and 1 with some probability. Just as when you roll a die and don't look at the outcome, or receive e-mail that you haven't yet read, you can view its state as a superposition of the possibilities. Now, this may sound like just flim-flam, but the fact is that this type of superposition is a kind of parallelism and that algorithms that make use of it can be faster than other algorithms. It is called randomized computation, and instead of superposition you can say that the bit is in a probabilistic state.

The difference between that and a qubit is that a qubit can have a fat set of possible superpositions with more properties. The set of probabilistic states of an ordinary bit is a line segment, because all there is a probability of 0 or 1. The set of states of a qubit is a round 3-dimensional ball. Now, probabilistic bit strings are more complicated and more interesting than just individual probabilistic bits, and the same is true of strings of qubits. If you can make qubits like this, then actually some computational tasks wouldn't be any easier than before, just as randomized algorithms don't help with all problems. But some computational problems, for example factoring numbers, have new quantum algorithms that are much faster than any known classical algorithm. It is not a matter of clock speed or Moore's law, because the first useful qubits could be fairly slow and expensive. It is only sort-of parallel computation, just as an algorithm that makes random choices is only in weak sense making all choices in parallel. But it is "randomized algorithms on steroids"; that's my favorite summary for outsiders.

Now the bad news. In order for a classical bit to be in a superposition, it has be a random choice that is secret from you. Once you look a flipped coin, the coin "collapses" to either heads for sure or tails for sure. The difference between that and a qubit is that in order for a qubit to work as one, its state has to be secret from the rest of the physical universe, not just from you. It has to be secret from wisps of air, from nearby atoms, etc. On the other hand, for qubits to be useful for a quantum computer, there has to be a way to manipulate them while keeping their state a secret. Otherwise its quantum randomness or quantum coherence is wrecked. Making qubits at all isn't easy, but it is done routinely. Making qubits that you can manipulate with quantum gates, without revealing what is in them to the physical environment, is incredibly difficult.

People don't know how to do that except in very limited toy demonstrations. But if they could do it well enough to make quantum computers, then some hard computational problems would be much easier for these computers. Others wouldn't be easier at all, and great deal is unknown about which ones can be accelerated and by how much. It would definitely have various effects on cryptography; it would break the widely used forms of public-key cryptography. But other kinds of public-key cryptography have been proposed that could be okay. Moreover quantum computing is related to the quantum key distribution technique which looks very safe, and secret-key cryptography would almost certainly still be fairly safe.

Jacquerie

Is it possible for a bit to have a third value other than 1 or 0, like "unknown"[NULL]? – Muir

Frank, there is a whole ball of values, or rather states. 1 is at the North pole of the ball, 0 is at the South pole, and you can have anything in between. There isn't a "third" state, there are a lot of states. I know that some of the books describe a "third" state, but it's wrong. It doesn't make any more sense than to say that the Earth has a "third" pole. – Jacquerie

@Greg: So, in your opinion, what would be the best way to implement quantum methods for ensuring privacy on the internet?..I'm currently using IE8 with "InPrivate" Browsing. Don't know how effective it is. It's supposed to prevent cookies and other things from being accessed. – Muir

My opinion is that quantum methods are irrelevant to practical security on the Internet for the forseeable future. If serious quantum computers existed, which for now they don't, then ssl connections (as in https) would have to be changed for all browsers. If you needed quantum key distribution, which for now you don't, then you would need a direct optic fiber line with special modems and no routing. Quantum computation and quantum key distribution are very important theoretical topics and very unimportant practical topics. – Jacquerie

@Greg: Can you build it? i.e. a quantum computer.. or a pseudo-quantum computer?.. what changes are needed to CPU's, memory and storage? – Muir

Here is a photo of a typical state-of-the-art apparatus: A laser and ion trap system that holds up to 10 qubits (but doesn't do all that much with them). It takes thousands of hours of labor to build it. softwoehr.com/softwoehr/images/codetalk/NIST_visit_20090818/… – Jacquerie

@Greg: Is it possible to software emulate quantum computing even though hardware uses two-state bits? – Muir

@Frank: You can only emulate a quantum computer very slowly. Each new qubit that you add makes the emulate twice as slow. So emulating more than about 30 qubits is impossible. That's the whole reason that quantum computation is interesting, that it's something new that can't be emulated. – Jacquerie

@Greg: But at least we do know the logic involved in properly emulating quantum computing, except we don't have fast enough hardware to support it? – Muir

Yes, we can write down a mathematical definition of quantum computation and very, very slowly emulate it. But it's not that we don't have "fast enough" hardware, it's that emulation in classical hardware inevitably scales very badly. The entire Google data center would not be able to simulate more than 60 qubits or so. The deeper point is that this is what makes quantum computation interesting: it's fundamentally different and it cannot be emulated efficiently. – Jacquerie

For more about current 128-qubit hardware, please take a look at my answer to another SO question: #433422 – Imponderable

@Imponderable I have to emphasize that quantum computing is a very, very theory-based area of research. As I see it, someone with a poor relationship to quantum computing theory is hardly someone who works in quantum computing at all. D-Wave has rather hobbled its reputation in the past few years for exactly that reason. I've been to several QC conferences, and I have seen very little interest in D-Wave. – Jacquerie

At present, has any research progress been made with QC? – Muir

@Frank There has been a significant amount of theoretical progress in understanding what quantum computers can do. Building quantum computers is much harder; there is no "Moore's Law" for that at the present time. But the quantum devices do also get better over time. – Jacquerie

In theory, could we software emulate a 1K qubit quantum computer? – Muir

@Frank If they are good qubits, then almost certainly not. For example, using Shor's algorithm, if you have 2n+3 qubits, you can quickly factor numbers with n binary digits. So if you had 2K qubits rather than 1K qubits, you could already beat world factorization records. However, no one thinks that factorization is the hardest possible thing that you could do with qubits. You could probably do something else even harder. No one has a plan for classically simulating more than 50 or so qubits. – Jacquerie

So like what things could we accomplish with 50 qubits?.. On another tangent, if drug manufacturers are able to turn on/off genes with medicines which target specific cells, can we develop a quantum computer (molecular computer), based on similar principles? – Muir

.. maybe we need to "think outside the box" to realize significant progress in the development of quantum computers? – Muir

@Frank Again, you don't really gain anything by simulating a tiny quantum computer with a classical computer. The whole point is to make a new type of computer that can run algorithms that classical computers can't run. I agree though that we need to think outside of the box to build quantum computers. That's what research always is, thinking outside of the box. (But just asking for a molecular computer is only a bare suggestion at some research angle. Who is to say whether a molecule would be the best construction of a qubit.) – Jacquerie

well, its tiny enough and electrons spin around the atoms, but probably impossible to control the decoherence to reliably read/write, even with the best nanotechnology available today.. perhaps it could be done with photons? – Muir

Answer 2

Yes, there is quantum encryption, by which if someone tries to spy on your communication, it destroys the datastream such that neither they nor you can read it.

However, the real power of quantum computing lies in that a qubit can have a superposition of 0 and 1. Big deal. However, if you have, say, eight qubits, you can now represent a superposition of all integers from 0 to 255. This lets you do some rather interesting things in polynomial instead of exponential time. Factorization of large numbers (IE, breaking RSA, etc.) is one of them.

Narghile

you mean like a no-cloning feature? – Muir

Answer 3

There are a number of applications of quantum computing.

One huge one is the ability to solve NP-hard problems in P-time, by using the indeterminacy of qubits to essentially brute-force the problem in parallel. (The struck-out sentence is false. Quantum computers do not work by brute-forcing all solutions in parallel, and they are not believed to be able to solve NP-complete problems in polynomial time. See e.g. here.)

Doublebank

Superposition of states don't lead to parallel processing. – Mychael

@Pierreten: well not parallel processing in the traditional sense, but it's a decent metaphor. When you apply quantum algorithms to a superposed state, it's essentially like applying the algorithm to each component of the superposition, all at the same time. – Randellrandene

The real tricks are in getting information back out of the resulting state. – Doublet

@detly; observation will collapse the wavefunction to discernable information. – Mychael

Oh god, this is distressing. PLEASE repeat after me: "Quantum computers cannot solve NP-hard problems in polynomial time. They do NOT work by trying all brute-force solutions in parallel!" I don't know who started this awful misconception, or why it persists. Please read Scott Aaronson's many entries on this matter, or just pick up a quantum computing textbook. (BQP is believed to be a strict subset of NP.) – Whimsy

The disclaimer is: you can only be sure that your solution is only N% percent correct (N maximized using an oracle function), but if the way to test the correctness of the solution has lower complexity than the problem (for example, multiplication vs factorization of two primes), you can just test it, and repeat if needed. – Boadicea

So then how can we harness and benefit from quantum computing? – Muir

Answer 4

The other factor where the word "quantum" computing is used regards an "entangled pair". Essentially if you can create an entangled pair of particles which have a physical "spin", quantum physics dictates that the spin on each electron will always be opposite.

If you could create an entangled pair and then separate them, you could use the device to transmit data without interception, by changing the spin on one of the particles. You can then create a signal which is modulated by the particle's information which is theoretically unbreakable, as you cannot know what spin was on the particles at any given time by intercepting the information in between the two signal points.

A whole lot of very interested organisations are researching this technique for secure communications.

Ammoniate

Answer 5

Just a update of quantum computing industry base on Greg Kuperberg's answer:

D-Wave 2 System is using quantum annealing.

The superposition quantum states will collapse to a unique state when a observation happened. The current technologies of quantum annealing is apply a physical force to 2 quantum bits, the force adds constrains to qubits so when observation happened, the qubit will have higher probability to collapse to a result that we are willing to see.

Reference:

1. How does a quantum machine work

Hayrack

Answer 6

I monitor recent non-peer reviewed articles on the subject, this is what I extrapolate from what I have read. a qubit, in addition to what has been said above. namely that they can hold values in superposition, they can also hold multiple bits, for example spin up/+ spin down/+ spin -/vertical , I need to abbreviate +H,-H,+V,-V Left+, LH,LV also not all of the combinations are valid and there are additional values that can be placed on the type of qubit each used similar to ram vs rom etc. photon with a wavelength, electron with a charge, photon with a charge, photon with a spin, you get the idea, some combinations are not valid and some require additional algorithms in order to pass the argument to the next variable(location where data is stored) or qubit(location of superposition of values to be returned, if you will simply because the use of wires is by necessity limited due to size and space. One of the greatest challenges is controlling or removing Q.(quantum) decoherence. This usually means isolating the system from its environment as interactions with the external world cause the system to decohere. November 2011 researchers factorised 143 using 4 qubits. that same year, D-Wave Systems announced the first commercial quantum annealer on the market by the name D-Wave One. The company claims this system uses a 128 qubit processor chipset.May 2013, Google Inc announced that it was launching the Q. AI. Lab, hopefully to boost AI. I really do Hope I didn't waste anyones time with things they already knew. If you learned something please up. As I can not yet comment, it really depends on what type of qubit you are working with to know the number of states for example the UNSW silicon Q. bit" vs a Diamond-neutron-valency or a SSD NMR Phosphorus - silicon vs Liquid NMR of the same.

Leidaleiden