6 ms·

I don't really understand quantum computing, and hopefully someone would shed light and let me know if my understanding is wrong. Isn't a qubit similar to a tra

I don't really understand quantum computing, and hopefully someone would shed light and let me know if my understanding is wrong. Isn't a qubit similar to a transistor that can hold more than 2 states and the implication is that it'll be faster than current SIMD operations?

roywiggins 7y ago
It's weirder than that. Some quantum algorithms offer a big-O speedup over classical ones. Shor's algorithm is O(n), which is categorically faster than any known classical algorithm for integer factoring. It's polynomial time, whereas the fastest classical algorithm is subexponential. For every subexponential algorithm, there will be some n at which Shor's algorithm will be faster, and some slightly higher n at which it's much, much, much faster. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm
seamyb88 7y ago
> Isn't a qubit similar to a transistor that can hold more than 2 states ... Not really. From an information theory perspective, holding two states is the most efficient way of computing. Or at least, there is no speed-up gained from doing computations in any other base than 2. Quantum computers can be in both states at the same time (as far as that interpretation of quantum mechanics goes). So, if you keep the qubits all in this superposition state, you can calculate multiple things at the same time.
- mrob 7y ago
  >From an information theory perspective, holding two states is the most efficient way of computing. Assuming the cost of operations on each digit is a multiple of its number of states, the most efficient base for computing with arbitrary numbers is 3, which is the closest integer to the optimal base e: https://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Ternary_computer https://en.wikipedia.org/wiki/Ternary_computer
  - seamyb88 7y ago
    Yes, you are correct. I said it all wrong. From a physical perspective, holding two states is the most efficient way of computing. I.e. the electronics required to compute in bases other than 2 involve higher power and present difficult challenges.
mattferderer 7y ago
I found this video to be a great explanation https://www.youtube.com/watch?v=OWJCfOvochA https://www.youtube.com/watch?v=OWJCfOvochA Explains to 5 different levels of CS knowledge.
deleted 7y ago
[deleted]
epicwhaleburger 7y ago
In no way am I qualified to talk about this with any sort of certainty, but I have been studying EE for the past 2 years and live in a house with a physicist who is probably far more well read in this topic. Classical computers are nice because they are predictable; if you want to order some product online, it would't be very helpful if the bit stream of data coming into your computer was fuzzy and muddled, making it hard to tell a 0 or a 1 apart. Quantum computing takes advantage of quantum properties such as the uncertainty principle and quantum entanglement to store bits in a state of being either a 0 or 1 until we "observe" the bit coming through (quantum bits -> qubit). This allows for algorithms, experiments, and other things quantum to be ran much faster than any classical computer since it can encode more data into a single bit. To minimize the fuzz in a q-computer, they freeze the sh*t out of it to keep the energy at a minimum, along with using conducting materials which excel at conducting heat away (like diamonds). I believe the spin of an electron is what determines the qubit value and when used in conjunction with quantum entanglement will affect other electrons that are already entangled. My little knowledge ends here but with this thought on quantum entanglement, you can see how flipping bits values respectively can allow for more ways to store information with the same amount of "stuff" remaining constant vs. a classical computer.
jfengel 7y ago
A quantum computer doesn't work much like a classical computer at all, so any analogy to transistors fails pretty quickly. One key aspect of that is that all of the qubits are entangled. The qubit isn't in more than two states, but in 2 states at once, and N qubits are in 2^N states at once. It's not quite as simple as that: you can't really just set up any algorithm in a quantum computer the way you would with a classical one. But for those problems amenable to quantum computation (including, notably, prime factoring), they can be solved very fast. With 2^53 qubits we should be able to factor some very, very large prime numbers.
- scottlocklin 7y ago
  You will find that this machine can't even factor the number 15 properly, as it's not error corrected, or a general purpose quantum computer. FWIIW nobody has factored the number 15 using quantum algorithms using the Shor algorithm yet; only using the subset of gates they know produces the numbers 3 and 5.
  - cthalupa 7y ago
    You keep repeating this, but as best as I can tell, it hasn't been factually accurate in a decade, unless you really want to quibble over the fact that they finished the calculation on a general purpose computer. https://www.schneier.com/blog/archives/2009/09/quantum_compute.html https://www.schneier.com/blog/archives/2009/09/quantum_compu... >Instead, it came up with an answer to the "order-finding routine," the "computationally hard" part of Shor's algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time. They weren't the first team to do this, either, they just miniaturized parts of the hardware.
    - scottlocklin 7y ago
      The result you cite doesn't even say what you think it says; in fact it directly says they didn't factor a damn thing. If I'm wrong and IBM's latest "quantum computer" can actually do the Shor algorithm on the number 15 using 4608 gate operations, I will publically eat one of my shoes like Werner Herzog. Assuming I can get someone else to take the other side of the bet, of course.
vsef 7y ago
An explanation in comic form with text by quantum computing researcher Scott Aaronson: https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3 QC is about setting up interference patterns between the qbits, it is fundamentally unlike classical computing. For some problems algorithms can be designed that use those interferences to compute things, like the famous Shor's algorithm for polynomial time prime factoring. QC speeds things up only in the cases where an asymptotically faster algorithm can be designed this way, it is not a general purpose parallelization mechanism. And we don't know many things it speeds up for sure! For example: we don't actually know that there isn't a classical polynomial time prime factors algorithm we haven't found. Here is a recent example of a quantum algorithm leading to the discovery of a classical algorithm that is equivalent to the quantum: https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/ https://www.quantamagazine.org/teenager-finds-classical-alte...
grumpy8 7y ago
The gist of it is: >> that can hold more than 2 states --> that can hold more than 2 states AT THE SAME TIME (in weird quantum conditions) So you're not trying 00, 01, 10, 11; you're trying [00|01|10 |11] at the same time, as well as other state in between 0 and 1.
PeCaN 7y ago
Since other people have already explained how qubits are not at all similar to transistors, I'd like to mention that it is not comparable at all to SIMD and there is no indication that quantum computers will be better at vector math than classical computers.

roywiggins 7y ago

It's weirder than that. Some quantum algorithms offer a big-O speedup over classical ones. Shor's algorithm is O(n), which is categorically faster than any known classical algorithm for integer factoring. It's polynomial time, whereas the fastest classical algorithm is subexponential. For every subexponential algorithm, there will be some n at which Shor's algorithm will be faster, and some slightly higher n at which it's much, much, much faster. https://en.wikipedia.org/wiki/Shor%27s_algorithm https://en.wikipedia.org/wiki/Shor%27s_algorithm

seamyb88 7y ago

> Isn't a qubit similar to a transistor that can hold more than 2 states ... Not really. From an information theory perspective, holding two states is the most efficient way of computing. Or at least, there is no speed-up gained from doing computations in any other base than 2. Quantum computers can be in both states at the same time (as far as that interpretation of quantum mechanics goes). So, if you keep the qubits all in this superposition state, you can calculate multiple things at the same time.

mrob 7y ago
>From an information theory perspective, holding two states is the most efficient way of computing. Assuming the cost of operations on each digit is a multiple of its number of states, the most efficient base for computing with arbitrary numbers is 3, which is the closest integer to the optimal base e: https://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Radix_economy https://en.wikipedia.org/wiki/Ternary_computer https://en.wikipedia.org/wiki/Ternary_computer
- seamyb88 7y ago
  Yes, you are correct. I said it all wrong. From a physical perspective, holding two states is the most efficient way of computing. I.e. the electronics required to compute in bases other than 2 involve higher power and present difficult challenges.

mattferderer 7y ago

I found this video to be a great explanation https://www.youtube.com/watch?v=OWJCfOvochA https://www.youtube.com/watch?v=OWJCfOvochA Explains to 5 different levels of CS knowledge.

deleted 7y ago

[deleted]

epicwhaleburger 7y ago

In no way am I qualified to talk about this with any sort of certainty, but I have been studying EE for the past 2 years and live in a house with a physicist who is probably far more well read in this topic. Classical computers are nice because they are predictable; if you want to order some product online, it would't be very helpful if the bit stream of data coming into your computer was fuzzy and muddled, making it hard to tell a 0 or a 1 apart. Quantum computing takes advantage of quantum properties such as the uncertainty principle and quantum entanglement to store bits in a state of being either a 0 or 1 until we "observe" the bit coming through (quantum bits -> qubit). This allows for algorithms, experiments, and other things quantum to be ran much faster than any classical computer since it can encode more data into a single bit. To minimize the fuzz in a q-computer, they freeze the sh*t out of it to keep the energy at a minimum, along with using conducting materials which excel at conducting heat away (like diamonds). I believe the spin of an electron is what determines the qubit value and when used in conjunction with quantum entanglement will affect other electrons that are already entangled. My little knowledge ends here but with this thought on quantum entanglement, you can see how flipping bits values respectively can allow for more ways to store information with the same amount of "stuff" remaining constant vs. a classical computer.

jfengel 7y ago

A quantum computer doesn't work much like a classical computer at all, so any analogy to transistors fails pretty quickly. One key aspect of that is that all of the qubits are entangled. The qubit isn't in more than two states, but in 2 states at once, and N qubits are in 2^N states at once. It's not quite as simple as that: you can't really just set up any algorithm in a quantum computer the way you would with a classical one. But for those problems amenable to quantum computation (including, notably, prime factoring), they can be solved very fast. With 2^53 qubits we should be able to factor some very, very large prime numbers.

scottlocklin 7y ago
You will find that this machine can't even factor the number 15 properly, as it's not error corrected, or a general purpose quantum computer. FWIIW nobody has factored the number 15 using quantum algorithms using the Shor algorithm yet; only using the subset of gates they know produces the numbers 3 and 5.
- cthalupa 7y ago
  You keep repeating this, but as best as I can tell, it hasn't been factually accurate in a decade, unless you really want to quibble over the fact that they finished the calculation on a general purpose computer. https://www.schneier.com/blog/archives/2009/09/quantum_compute.html https://www.schneier.com/blog/archives/2009/09/quantum_compu... >Instead, it came up with an answer to the "order-finding routine," the "computationally hard" part of Shor's algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time. They weren't the first team to do this, either, they just miniaturized parts of the hardware.
  - scottlocklin 7y ago
    The result you cite doesn't even say what you think it says; in fact it directly says they didn't factor a damn thing. If I'm wrong and IBM's latest "quantum computer" can actually do the Shor algorithm on the number 15 using 4608 gate operations, I will publically eat one of my shoes like Werner Herzog. Assuming I can get someone else to take the other side of the bet, of course.

vsef 7y ago

An explanation in comic form with text by quantum computing researcher Scott Aaronson: https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3 QC is about setting up interference patterns between the qbits, it is fundamentally unlike classical computing. For some problems algorithms can be designed that use those interferences to compute things, like the famous Shor's algorithm for polynomial time prime factoring. QC speeds things up only in the cases where an asymptotically faster algorithm can be designed this way, it is not a general purpose parallelization mechanism. And we don't know many things it speeds up for sure! For example: we don't actually know that there isn't a classical polynomial time prime factors algorithm we haven't found. Here is a recent example of a quantum algorithm leading to the discovery of a classical algorithm that is equivalent to the quantum: https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/ https://www.quantamagazine.org/teenager-finds-classical-alte...

grumpy8 7y ago

The gist of it is: >> that can hold more than 2 states --> that can hold more than 2 states AT THE SAME TIME (in weird quantum conditions) So you're not trying 00, 01, 10, 11; you're trying [00|01|10 |11] at the same time, as well as other state in between 0 and 1.

PeCaN 7y ago

Since other people have already explained how qubits are not at all similar to transistors, I'd like to mention that it is not comparable at all to SIMD and there is no indication that quantum computers will be better at vector math than classical computers.