6 ms·

Largest quantum computer yet: 14 qubits

46 points by SoftwarePatent 16y ago

SoftwarePatent 16y ago
You should care about quantum computers because they can factor numbers in polynomial time, which breaks RSA public-key encryption. http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm
- younata 16y ago
  Ok, forgive my ignorance, but why is it that quantum algorithms can ONLY run on quantum computers? Is it the fact that qubits can have three states? If that is the case (which it likely isn't), why is base 3 better for this work than base 2?
  - deleted 16y ago
    [deleted]
  - SoftwarePatent 16y ago
    Quantum computers make use of quantum mechanics. So things like entanglement and decoherence are essential to the algorithms. It has nothing to do with base 2.
  - sgk284 16y ago
    It's not so much 3 states, as it is two states and a superposition of both states, meaning that the qubit is effectively both a 0 and a 1 at the same time.
  - vmind 16y ago
    Basically: Qubits (sort of) encode all possible states that a standard string of bits can take at the same time as a superposition, such that when you measure them, you have a possibility of observing each possible setting of the bits. You can manipulate the possibility of observing certain states by performing operations on the bits (which are effectively interference). So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. In order to be sure of a result, you need to repeat the calculation to get a desired confidence (or just check the answer directly if that would be faster).
    - dcosson 16y ago
      > So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. Not necessarily, some quantum algorithms give an answer with 100% probability (like the Deutch-Josza algorithm). You're right in that the two most interesting ones (Grover's and Shor's algorithms) are probabilistic, though.
  - devinj 16y ago
    No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html which discusses simulating Shor's algorithm on a classical computer. The reason for the exponential is that the bits are all in a superposition of all possible states (so for a 14-bit register, that's a superposition of 2 to the 14 states), which operations all act on. Or something like that. I'm not really that clear on the details. :(
    - bdhe 16y ago
      > Or something like that. I'm not really that clear on the details. :( Your intuition is correct. Quantum algorithms seem to perform better than classic algorithms because there are certain operations (like fourier transforms) that can be performed exponentially faster (as of today) than classic algorithms. It is still unknown however whether or not we can simulate quantum computations classically without exponential blowup otherwise it would resolve major open questions in complexity theory.
  - masterzora 16y ago
    Obviously that isn't the case; if it were we'd simply roll out ternary computers, which have been used before. I'm no physicist, and my knowledge of quantum is mostly memories of an intro course I took 5 years ago, so I hope someone with a bit more knowledge can come and fill in the gaps here. Nevertheless, the basic principle is that quantum superposition allows us to parallelise things with relatively reasonable space requirements.
- cperciva 16y ago
  I think 14 qubits is large enough to factor 21. Pretty sure it can't factor 35 yet, though.
- procrastitron 16y ago
  Restricting the problem to a fixed size input makes factoring an O(1) operation; so I still don't see what all the fuss is about. Unless you know a way of extending this to handle an arbitrary amount of I/O then it's just a way of implementing nondeterministic finite state machines; which are no more powerful than deterministic finite state machines.
  - pmjordan 16y ago
    Rather than downvoting you to oblivion, I'll point out that "Restricting the problem to a fixed size input makes factoring an O(1) operation" makes no sense. Sorting an array of N items using a comparison sort has a lower complexity bound of O(N log(N)) in the worst case. Yes, of course that becomes O(1) if you say N is constant, but that's really not helpful at all.
- qntm 16y ago
  Which is why you should also care about post-quantum cryptography: http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography
michael_nielsen 16y ago
I once asked one of the leading quantum computing experimentalists how many qubits he could completely control in the lab. He immediately and emphatically replied "none". I always think of this when I see headlines touting achievements such as a 14-qubit quantum computer, or stories about controlled entanglement of 14 qubits. These make good narrative hooks for an article, but they can also hide a lot. EDIT: A free pdf of a draft of the paper is at: http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.6126v2.pdf http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.6126v2.pdf. A quick skim suggests that at 14 qubits the state they actually prepare in the lab is, indeed, not very similar to the state they intend to prepare, with a reported fidelity of about 50%. That's the same fidelity they'd get if they just prepared an all |0> state. While the paper reports terrifically interesting work, this and many other details in the paper suggest quite a subtle picture.
- Locke1689 16y ago
  While 14 qubits is an impressive achievement, one of the biggest problems now seems to be maintaining coherence for more than a few nano or microseconds.
  - bhrgunatha 16y ago
    Yes the post title is misleading. They haven't produced a 14 qubit quantum computer able to do any computation, but they have produced a single quantum register of 14 qubits with (according to the PDF linked by michael_nielsen) < 50% coherence - about 50% fidelity. Less impressive sounding but still pretty amazing.
- archgoon 16y ago
  >He immediately and emphatically replied "none". This raises the question, what counts as "completely controlled"? What is typically meant when they say "Built X qubit quantum computer?"
- dcosson 16y ago
  Thanks for posting the link. The GHZ state they created is technically entangled (in the way that Einstein was worried about entanglement, where if you took one of the 14 qubits far away from the rest, you could measure it and instantly have knowledge of the other 13 qubits, which seemingly violates special relativity). However, even ignoring the fact that this was only to 50% fidelity, it is also only a superposition of two states. To run, say, the phase estimation algorithm (which is the heavy-lifting part of Shor's algorithm), you need an equal superposition of all 2^14 states, which is obviously a lot different. Anyway, I agree with your analysis - this is a great accomplishment, but we are still further from having true quantum computers than the news reports would make it seem.

You should care about quantum computers because they can factor numbers in polynomial time, which breaks RSA public-key encryption. http://en.wikipedia.org/wiki/Shor%27s_algorithm http://en.wikipedia.org/wiki/Shor%27s_algorithm

younata 16y ago
Ok, forgive my ignorance, but why is it that quantum algorithms can ONLY run on quantum computers? Is it the fact that qubits can have three states? If that is the case (which it likely isn't), why is base 3 better for this work than base 2?
- deleted 16y ago
  [deleted]
- SoftwarePatent 16y ago
  Quantum computers make use of quantum mechanics. So things like entanglement and decoherence are essential to the algorithms. It has nothing to do with base 2.
- sgk284 16y ago
  It's not so much 3 states, as it is two states and a superposition of both states, meaning that the qubit is effectively both a 0 and a 1 at the same time.
- vmind 16y ago
  Basically: Qubits (sort of) encode all possible states that a standard string of bits can take at the same time as a superposition, such that when you measure them, you have a possibility of observing each possible setting of the bits. You can manipulate the possibility of observing certain states by performing operations on the bits (which are effectively interference). So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. In order to be sure of a result, you need to repeat the calculation to get a desired confidence (or just check the answer directly if that would be faster).
  - dcosson 16y ago
    > So a quantum calculation is more a probabilistic restriction on which state you want, rather than a direct calculation. Not necessarily, some quantum algorithms give an answer with 100% probability (like the Deutch-Josza algorithm). You're right in that the two most interesting ones (Grover's and Shor's algorithms) are probabilistic, though.
- devinj 16y ago
  No, they can run on quantum computers, but to properly simulate a quantum computer, you may need exponential space/time. Googling for supporting data brought up http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html http://alumni.imsa.edu/~matth/quant/433/shor-par/node19.html which discusses simulating Shor's algorithm on a classical computer. The reason for the exponential is that the bits are all in a superposition of all possible states (so for a 14-bit register, that's a superposition of 2 to the 14 states), which operations all act on. Or something like that. I'm not really that clear on the details. :(
  - bdhe 16y ago
    > Or something like that. I'm not really that clear on the details. :( Your intuition is correct. Quantum algorithms seem to perform better than classic algorithms because there are certain operations (like fourier transforms) that can be performed exponentially faster (as of today) than classic algorithms. It is still unknown however whether or not we can simulate quantum computations classically without exponential blowup otherwise it would resolve major open questions in complexity theory.
- masterzora 16y ago
  Obviously that isn't the case; if it were we'd simply roll out ternary computers, which have been used before. I'm no physicist, and my knowledge of quantum is mostly memories of an intro course I took 5 years ago, so I hope someone with a bit more knowledge can come and fill in the gaps here. Nevertheless, the basic principle is that quantum superposition allows us to parallelise things with relatively reasonable space requirements.
cperciva 16y ago
I think 14 qubits is large enough to factor 21. Pretty sure it can't factor 35 yet, though.
procrastitron 16y ago
Restricting the problem to a fixed size input makes factoring an O(1) operation; so I still don't see what all the fuss is about. Unless you know a way of extending this to handle an arbitrary amount of I/O then it's just a way of implementing nondeterministic finite state machines; which are no more powerful than deterministic finite state machines.
- pmjordan 16y ago
  Rather than downvoting you to oblivion, I'll point out that "Restricting the problem to a fixed size input makes factoring an O(1) operation" makes no sense. Sorting an array of N items using a comparison sort has a lower complexity bound of O(N log(N)) in the worst case. Yes, of course that becomes O(1) if you say N is constant, but that's really not helpful at all.
qntm 16y ago
Which is why you should also care about post-quantum cryptography: http://en.wikipedia.org/wiki/Post-quantum_cryptography http://en.wikipedia.org/wiki/Post-quantum_cryptography

michael_nielsen 16y ago

I once asked one of the leading quantum computing experimentalists how many qubits he could completely control in the lab. He immediately and emphatically replied "none". I always think of this when I see headlines touting achievements such as a 14-qubit quantum computer, or stories about controlled entanglement of 14 qubits. These make good narrative hooks for an article, but they can also hide a lot. EDIT: A free pdf of a draft of the paper is at: http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.6126v2.pdf http://arxiv.org/PS_cache/arxiv/pdf/1009/1009.6126v2.pdf. A quick skim suggests that at 14 qubits the state they actually prepare in the lab is, indeed, not very similar to the state they intend to prepare, with a reported fidelity of about 50%. That's the same fidelity they'd get if they just prepared an all |0> state. While the paper reports terrifically interesting work, this and many other details in the paper suggest quite a subtle picture.

Locke1689 16y ago
While 14 qubits is an impressive achievement, one of the biggest problems now seems to be maintaining coherence for more than a few nano or microseconds.
- bhrgunatha 16y ago
  Yes the post title is misleading. They haven't produced a 14 qubit quantum computer able to do any computation, but they have produced a single quantum register of 14 qubits with (according to the PDF linked by michael_nielsen) < 50% coherence - about 50% fidelity. Less impressive sounding but still pretty amazing.
archgoon 16y ago
>He immediately and emphatically replied "none". This raises the question, what counts as "completely controlled"? What is typically meant when they say "Built X qubit quantum computer?"
dcosson 16y ago
Thanks for posting the link. The GHZ state they created is technically entangled (in the way that Einstein was worried about entanglement, where if you took one of the 14 qubits far away from the rest, you could measure it and instantly have knowledge of the other 13 qubits, which seemingly violates special relativity). However, even ignoring the fact that this was only to 50% fidelity, it is also only a superposition of two states. To run, say, the phase estimation algorithm (which is the heavy-lifting part of Shor's algorithm), you need an equal superposition of all 2^14 states, which is obviously a lot different. Anyway, I agree with your analysis - this is a great accomplishment, but we are still further from having true quantum computers than the news reports would make it seem.