5 ms·

Quantum computers will be good at a specific range of problems where interference can be taken advantage of. It drives me crazy how many people think they just

Quantum computers will be good at a specific range of problems where interference can be taken advantage of. It drives me crazy how many people think they just go into a superposition and calculate all outcomes at the same time. It doesn't work that way. And we still have to scale them with proper error correction. Who knows what the timeline for this looks like. Anyone who assumes "Moore's Law" isn't taking into consideration the fact that scaling here isn't as simple as multiplying the number of transistors in parallel. To be useful they have to achieve entanglement between new qubits. Plus error correction and isolation have to also be scaled with that.

wlesieutre 9y ago
SMBC has a great comic on how quantum computers work https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
- wybiral 9y ago
  That's a good comic, thanks! "Wait a minute... That means a qubit corresponds to a unit vector in two-dimensional Hilbert space!" And quantum gates/operations on qubits are just unitary linear transformations on those vector spaces...
  - asdlllkasdasd 9y ago
    An unintuitive but important fact is that n qubits do not correspond to n unit vectors in two-dimensional Hilbert space (but rather to one unit vector in 2^n-dimensional Hilbert space).
    - tome 9y ago
      And that's how entanglement arises, presumably.
      - urgoroger 9y ago
        I think you have the right idea but the wrong terminology. A n qubit system requires amplitudes (probabilities) for all 2^n possible basis states. For example, the representation we can give to a 2-qubit system is just a probability (technically an amplitude) associated with each of states 00, 01, 10, and 11. It's not really fancy or hard to see how this increases exponentially. Here's an example with classical randomness (and has a close quantum analogue). If you have two closed boxes with coins in them and shake both around so that the coins flip around in the in such a way that they land 50/50 on each side, you could represent that state of the system as [1/4, 1/4, 1/4, 1/4], that is, each possible state of the system of two coins (heads head, heads tail, tail head, and tail tail), has 1/4 chance of being observed when you open the boxes. Note that entanglement refers to the idea that two bits can be correlated. That is, the state of one is correlated with the state of another in some sense. In the example I just gave, the coins are not entangled, since the observation of one of the coins does not affect the probability of what the other coin could be. In mathematics we say this is possible if the state of the 2-coin system [1/4 1/4 1/4 1/4] can be written as a tensor product of the constituent 1-coin systems [1/2 1/2] and [1/2 1/2], which it can (entanglement refers to a state where this factorization isn't possible). That said, we can achieve entanglement with the coins too, by somehow getting a state vector like [1/2 0 0 1/2] (50% chance that both coins are heads and 50% chance both are tails), which cannot be written as a tensor product of two 1-coin states. Moreover, if you open one box and see its a heads coin, you know the other box must also have a head coin. That's what is meant by 'correlation'. To product such a state of the coin boxes, I guess you would need a third party or something to put the two coins in the boxes and delivering them to you. My conclusion is, entanglement doesn't have to do too much with the exponential size of representation n-qubit states, and I hope I gave a good example of what entanglement kind of really means. While (randomized) classical analogues to quantum effects are not really perfect, I think they demonstrate these effects more understandably.
        asdlllkasdasd 9y ago
        Parent is correct — entanglement is exactly due to the fact that there exist more vectors in Hilbert space than tensor products (~ tuples) of unit vectors.
- java-man 9y ago
  hilarious!
openasocket 9y ago
From a computational complexity standpoint, it's not even clear if quantum computing is actually faster. The discrete log problem and integer factoring problem aren't known to be NP-complete, so even assuming P != NP it's possible there are polynomial time algorithms for factoring and discrete log on classical computers as well. BQP vs. P is still, IIRC, unresolved. Though, from a practical standpoint, I have a feeling that, regardless of how the computational classes shake out, the quantum Fourier transform will prove to be faster than classical techniques. And possibly Grover's algorithm, though its results are somewhat less dramatic.
- Robotbeat 9y ago
  We are certain that quantum computing is much faster for simulating quantum phenomenon. And while it is difficult to show that quantum computing is faster for even some classical computations, it can be shown. Here's a skeptical eye on quantum algorithms: "Read the Fine Print" by Scott Aaronson: https://www.nature.com/articles/nphys3272 https://www.nature.com/articles/nphys3272 PDF: https://pdfs.semanticscholar.org/dfe4/d76e3fc27304a984a5daf1be530401724c25.pdf https://pdfs.semanticscholar.org/dfe4/d76e3fc27304a984a5daf1...
mtgx 9y ago
There was a recent post on BBC where the academics said their quantum computer will scale through modules. So they have to get a module right, and after that it will be "easy" to scale. http://www.bbc.com/news/av/technology-42426121/quantum-computing-modular-system-announced http://www.bbc.com/news/av/technology-42426121/quantum-compu... The recent UNSW silicon architecture announcement included something similar to that (480 qubit chip module that scales). Plus, they said they have an error-correction algorithm that will scale to millions of qubits. https://newsroom.unsw.edu.au/news/science-tech/complete-design-silicon-quantum-computer-chip-unveiled https://newsroom.unsw.edu.au/news/science-tech/complete-desi... Google has also suggested that they just need to get the stability of the first qubits right and then scaling them will be easier: https://www.wired.com/2014/09/martinis/ https://www.wired.com/2014/09/martinis/ In that post Martinis actually hoped they'd double the number of qubits every year, but I think it's been closer to 1.5-2 years, for both Google and IBM. Google plans to announce the rumored 49 qubits quantum computer next March. D-Wave was able to double the number of qubits every year in their first four years, and now it seems to double every 2 years. I think D-Wave's capabilities have only improved significantly, rather than regressed with the number of qubits. We don't know yet if that's true for Google and IBM, but I would imagine it is.
- Robotbeat 9y ago
  D-Wave's computer is fundamentally different than other quantum computers. The D-Wave is a quantum annealling computer. And for a while, there was some question whether what it was doing could actually be described fully classically, though now I think the consensus is that there is some quantum effect. Although classical or quantum, there could still be a practical speed up over the typical conventional computers. The idea is to use them for optimization problems. But they aren't a straightforward mapping to the usual quantum computer, and so cannot be directly compared. To me, it's like comparing an analogue and a digital computer.
Robotbeat 9y ago
It turns out, though, that those few problems are pretty common. FFT is O(d log d) classically, and O((log d)^2) Quantum mechanically. Gaussian elimination (used to find eigenvectors and eigenvalues) is O(d^3) or O(s * d^2) for classical (non-sparse and sparse, respectively) versus O((log d)^2) for Quantum. (And similar speed up for Matrix inversion.) FFT? Matrix inversion? Gaussian elimination? Super common. And in the case of Gaussian elimination, it gets pretty hard pretty fast. You're right that we still have to scale with proper error correction, but the fact that quantum error correction is possible is very good news for the future of quantum computing. And the best, ~50-bit quantum computers are approaching what is needed for a fully error corrected qubit, although proper connectivity needs some work. So you're right to be wary of the current status of quantum computing, but I think you're wrong about Moore's Law, here. Qubits can be and are made with photolithographically scalable techniques today with error rates that approach what's needed for error correction, even taking into account some of the problems that integration causes for integration. And, in fact, error correction is what enables us to scale quantum computing (although there are still some calculations we can do without error correction). I do think we're pretty close to a threshold, here, with quantum computing. We are probably under one or two years away from "quantum supremacy," if you accept having a quantum computer too sophisticated to reliably simulate classically. Some resources: Google talk about Quantum computing engineering work being done at MIT Lincoln: https://www.youtube.com/watch?v=Jgc20Xc8IpA https://www.youtube.com/watch?v=Jgc20Xc8IpA This man's blog is fantastic: https://medium.com/@decodoku/latest https://medium.com/@decodoku/latest ...with a usefully skeptical take here: https://medium.com/@decodoku/quantum-computing-is-not-as-close-as-you-might-have-heard-e26ad533409 https://medium.com/@decodoku/quantum-computing-is-not-as-clo... We aren't 3 years away from breaking encryption using Shor's Algorithm. We're probably at least a decade away. But there ARE a bunch of uses for quantum computing that don't require as many qubits. A few hundred physical qubits is still enough to do things that wouldn't be feasible with classical computing.
- red75prime 9y ago
  Let's hope we will not find ultimate computational limitations of our Universe's physics instead.
- urgoroger 9y ago

wlesieutre 9y ago

SMBC has a great comic on how quantum computers work https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3

wybiral 9y ago
That's a good comic, thanks! "Wait a minute... That means a qubit corresponds to a unit vector in two-dimensional Hilbert space!" And quantum gates/operations on qubits are just unitary linear transformations on those vector spaces...
- asdlllkasdasd 9y ago
  An unintuitive but important fact is that n qubits do not correspond to n unit vectors in two-dimensional Hilbert space (but rather to one unit vector in 2^n-dimensional Hilbert space).
  - tome 9y ago
    And that's how entanglement arises, presumably.
    - urgoroger 9y ago
      I think you have the right idea but the wrong terminology. A n qubit system requires amplitudes (probabilities) for all 2^n possible basis states. For example, the representation we can give to a 2-qubit system is just a probability (technically an amplitude) associated with each of states 00, 01, 10, and 11. It's not really fancy or hard to see how this increases exponentially. Here's an example with classical randomness (and has a close quantum analogue). If you have two closed boxes with coins in them and shake both around so that the coins flip around in the in such a way that they land 50/50 on each side, you could represent that state of the system as [1/4, 1/4, 1/4, 1/4], that is, each possible state of the system of two coins (heads head, heads tail, tail head, and tail tail), has 1/4 chance of being observed when you open the boxes. Note that entanglement refers to the idea that two bits can be correlated. That is, the state of one is correlated with the state of another in some sense. In the example I just gave, the coins are not entangled, since the observation of one of the coins does not affect the probability of what the other coin could be. In mathematics we say this is possible if the state of the 2-coin system [1/4 1/4 1/4 1/4] can be written as a tensor product of the constituent 1-coin systems [1/2 1/2] and [1/2 1/2], which it can (entanglement refers to a state where this factorization isn't possible). That said, we can achieve entanglement with the coins too, by somehow getting a state vector like [1/2 0 0 1/2] (50% chance that both coins are heads and 50% chance both are tails), which cannot be written as a tensor product of two 1-coin states. Moreover, if you open one box and see its a heads coin, you know the other box must also have a head coin. That's what is meant by 'correlation'. To product such a state of the coin boxes, I guess you would need a third party or something to put the two coins in the boxes and delivering them to you. My conclusion is, entanglement doesn't have to do too much with the exponential size of representation n-qubit states, and I hope I gave a good example of what entanglement kind of really means. While (randomized) classical analogues to quantum effects are not really perfect, I think they demonstrate these effects more understandably.
      - asdlllkasdasd 9y ago
        Parent is correct — entanglement is exactly due to the fact that there exist more vectors in Hilbert space than tensor products (~ tuples) of unit vectors.
java-man 9y ago
hilarious!

openasocket 9y ago

From a computational complexity standpoint, it's not even clear if quantum computing is actually faster. The discrete log problem and integer factoring problem aren't known to be NP-complete, so even assuming P != NP it's possible there are polynomial time algorithms for factoring and discrete log on classical computers as well. BQP vs. P is still, IIRC, unresolved. Though, from a practical standpoint, I have a feeling that, regardless of how the computational classes shake out, the quantum Fourier transform will prove to be faster than classical techniques. And possibly Grover's algorithm, though its results are somewhat less dramatic.

Robotbeat 9y ago
We are certain that quantum computing is much faster for simulating quantum phenomenon. And while it is difficult to show that quantum computing is faster for even some classical computations, it can be shown. Here's a skeptical eye on quantum algorithms: "Read the Fine Print" by Scott Aaronson: https://www.nature.com/articles/nphys3272 https://www.nature.com/articles/nphys3272 PDF: https://pdfs.semanticscholar.org/dfe4/d76e3fc27304a984a5daf1be530401724c25.pdf https://pdfs.semanticscholar.org/dfe4/d76e3fc27304a984a5daf1...

mtgx 9y ago

There was a recent post on BBC where the academics said their quantum computer will scale through modules. So they have to get a module right, and after that it will be "easy" to scale. http://www.bbc.com/news/av/technology-42426121/quantum-computing-modular-system-announced http://www.bbc.com/news/av/technology-42426121/quantum-compu... The recent UNSW silicon architecture announcement included something similar to that (480 qubit chip module that scales). Plus, they said they have an error-correction algorithm that will scale to millions of qubits. https://newsroom.unsw.edu.au/news/science-tech/complete-design-silicon-quantum-computer-chip-unveiled https://newsroom.unsw.edu.au/news/science-tech/complete-desi... Google has also suggested that they just need to get the stability of the first qubits right and then scaling them will be easier: https://www.wired.com/2014/09/martinis/ https://www.wired.com/2014/09/martinis/ In that post Martinis actually hoped they'd double the number of qubits every year, but I think it's been closer to 1.5-2 years, for both Google and IBM. Google plans to announce the rumored 49 qubits quantum computer next March. D-Wave was able to double the number of qubits every year in their first four years, and now it seems to double every 2 years. I think D-Wave's capabilities have only improved significantly, rather than regressed with the number of qubits. We don't know yet if that's true for Google and IBM, but I would imagine it is.

Robotbeat 9y ago
D-Wave's computer is fundamentally different than other quantum computers. The D-Wave is a quantum annealling computer. And for a while, there was some question whether what it was doing could actually be described fully classically, though now I think the consensus is that there is some quantum effect. Although classical or quantum, there could still be a practical speed up over the typical conventional computers. The idea is to use them for optimization problems. But they aren't a straightforward mapping to the usual quantum computer, and so cannot be directly compared. To me, it's like comparing an analogue and a digital computer.

Robotbeat 9y ago

It turns out, though, that those few problems are pretty common. FFT is O(d log d) classically, and O((log d)^2) Quantum mechanically. Gaussian elimination (used to find eigenvectors and eigenvalues) is O(d^3) or O(s * d^2) for classical (non-sparse and sparse, respectively) versus O((log d)^2) for Quantum. (And similar speed up for Matrix inversion.) FFT? Matrix inversion? Gaussian elimination? Super common. And in the case of Gaussian elimination, it gets pretty hard pretty fast. You're right that we still have to scale with proper error correction, but the fact that quantum error correction is possible is very good news for the future of quantum computing. And the best, ~50-bit quantum computers are approaching what is needed for a fully error corrected qubit, although proper connectivity needs some work. So you're right to be wary of the current status of quantum computing, but I think you're wrong about Moore's Law, here. Qubits can be and are made with photolithographically scalable techniques today with error rates that approach what's needed for error correction, even taking into account some of the problems that integration causes for integration. And, in fact, error correction is what enables us to scale quantum computing (although there are still some calculations we can do without error correction). I do think we're pretty close to a threshold, here, with quantum computing. We are probably under one or two years away from "quantum supremacy," if you accept having a quantum computer too sophisticated to reliably simulate classically. Some resources: Google talk about Quantum computing engineering work being done at MIT Lincoln: https://www.youtube.com/watch?v=Jgc20Xc8IpA https://www.youtube.com/watch?v=Jgc20Xc8IpA This man's blog is fantastic: https://medium.com/@decodoku/latest https://medium.com/@decodoku/latest ...with a usefully skeptical take here: https://medium.com/@decodoku/quantum-computing-is-not-as-close-as-you-might-have-heard-e26ad533409 https://medium.com/@decodoku/quantum-computing-is-not-as-clo... We aren't 3 years away from breaking encryption using Shor's Algorithm. We're probably at least a decade away. But there ARE a bunch of uses for quantum computing that don't require as many qubits. A few hundred physical qubits is still enough to do things that wouldn't be feasible with classical computing.

red75prime 9y ago
Let's hope we will not find ultimate computational limitations of our Universe's physics instead.
urgoroger 9y ago