6 ms·

What's the size needed for cracking large-primes based encryption? If not at 100 qubits, what are some useful calculations that we can do at that size?

deepGem 8y ago
So the number of raw qubits are in the order of a million for large prime factorization or to make Shor's algorithm a reality. This is because the physical qubits are highly unstable and prone to errors. The error correction methodologies will result in a fault-tolerant logical qubit. Depending on the error correction algorithm, the ratio of logical: data/physical qubit is 1:1000 at the minimum. You need 4000 logical qubits at least for large prime factorization give or take 4 million raw qubits.
- amelius 8y ago
  How fast do you think the number of qubits will grow over the coming years? Will it be exponential, like Moore's law?
  - misterprime 8y ago
    There was an AMA not long ago with someone in the quantum computer industry and iirc he stated that it isn't certain if we even can go that high. Guessing how fast that will happen is not reasonable at this point.
- bscphil 8y ago
  This is probably a dumb question, but could you spread out the error correction in time? I know it's hard to create very large entangled systems, so would it be possible/easier to do the calculation with 4000 real qubits 1000 times and use the repetition for error correction? (Checking for correct factorization is easy, after all.)
  - simcop2387 8y ago
    That's been one strategy I've seen mentioned in regards to Shor's algorithm many times. Since there's the probability of an error, you still have to check it and rerun it a few times until you confirm the right answer. That's still many times faster than you'd get conventionally, so it's a reasonable trade off. But it doesn't address the possibility that you can't entangle enough qubits to begin with, or keep them stable long enough to actually perform the calculations, which is where the error correction stuff comes in. I don't know enough about the challenges there to comment on how many you'd need (though 1000:1 seems high to my naive intuition, i'd guess maybe 10-100 for magnitude myself).
    - sir_kin 8y ago
      For more info on that 1000:1 ratio, see [1]. [1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem https://en.wikipedia.org/wiki/Quantum_threshold_theorem
  - mirekrusin 8y ago
    Calculation on quantum state is already spread in time. Each time you calculate something you basically take snapshot of the state. Then you do it again. After many trials patterns emerge - that’s when you start reading your answer - which is always probabilistic.
- wiz21c 8y ago
  >>> qubits are highly unstable newbie question : are they naturally instable (so we won't fix that) or is it just because we don't master them well enough right now (and we'll fix them "soon") ?
  - deepGem 8y ago
    It's the former. They can be made stable at super conducting temperatures but not completely. There will always be errors. From what I can understand you cant fully eliminate the errors. I donno may be some new superconducting temp might make them stable but that's a wild guess.
dzhiurgis 8y ago
A lot of things regarding chemistry and biology - finding catalysts for nitrate fertiliser production (uses 5% of worlds power), perhaps some catalysts in cement production (my idea), invention of new medicines, either due to better cell simulations or (my idea) faster protein folding.
- aaavl2821 8y ago
  Is the bottleneck preventing better cell simulations computational or lack of data / insufficient understanding of biology to inform a predictive model?
  - thatcherc 8y ago
    My understanding as a physics undergrad is that we can write down the 'equations of motion' of molecular systems with Hamiltonians describing the energies and correlations of the electrons in a system, but they very quickly become intractably difficult to solve. You're trying to solve a very, very big eigenvalue problem. However, with the right kind of quantum computer or quantum simulator, you could construct a system of qubits that is described by the exact same Hamiltonian. That way, the quantum state of your qubits and your original system would behave in exactly the same way. Then, you just let the qubits evolve in time and read out the system's state at the end. Do that a bunch of times and you'll see an average picture of what the original system you're modelling (protein or something) would do. So to recap - we can get around the difficult compute bottleneck caused by the desire to perform high-fidelity physics simulations by creating a system that follows the same rules and which we can probe much more easily.
  - BookmarkSaver 8y ago
    Not an expert, but my understanding is that while better knowledge/models of the biology might be useful, ultimately it's just a massive computational project to test out and optimize protein folding and such complex chemical behavior. The physics/chemistry and biology are understood well enough, there are just nearly countless paths to explore making it a huge problem.
    - 8y ago
rurban 8y ago
2048 would break current crypto, >20 would help solving most unsolvable NP hard problems.
- sir_kin 8y ago
  2018 LOGICAL qubits would break current crypto. But qubits decohere extremely fast, so you need error correcting schemes. Current estimates require 1000 - 10000 physical qubits per logical error corrected qubit. [1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem https://en.wikipedia.org/wiki/Quantum_threshold_theorem
  - rurban 8y ago
    No, no one cares about those HW problems. To break RSA keys you need 0 error correction. You only need >2000 entangled qbits, and they either produce a correct result or not. For other calculations you might need error correction, but this leads to nowhere with current technology. What the Chinese did was groundbreaking.

deepGem 8y ago

So the number of raw qubits are in the order of a million for large prime factorization or to make Shor's algorithm a reality. This is because the physical qubits are highly unstable and prone to errors. The error correction methodologies will result in a fault-tolerant logical qubit. Depending on the error correction algorithm, the ratio of logical: data/physical qubit is 1:1000 at the minimum. You need 4000 logical qubits at least for large prime factorization give or take 4 million raw qubits.

amelius 8y ago
How fast do you think the number of qubits will grow over the coming years? Will it be exponential, like Moore's law?
- misterprime 8y ago
  There was an AMA not long ago with someone in the quantum computer industry and iirc he stated that it isn't certain if we even can go that high. Guessing how fast that will happen is not reasonable at this point.
bscphil 8y ago
This is probably a dumb question, but could you spread out the error correction in time? I know it's hard to create very large entangled systems, so would it be possible/easier to do the calculation with 4000 real qubits 1000 times and use the repetition for error correction? (Checking for correct factorization is easy, after all.)
- simcop2387 8y ago
  That's been one strategy I've seen mentioned in regards to Shor's algorithm many times. Since there's the probability of an error, you still have to check it and rerun it a few times until you confirm the right answer. That's still many times faster than you'd get conventionally, so it's a reasonable trade off. But it doesn't address the possibility that you can't entangle enough qubits to begin with, or keep them stable long enough to actually perform the calculations, which is where the error correction stuff comes in. I don't know enough about the challenges there to comment on how many you'd need (though 1000:1 seems high to my naive intuition, i'd guess maybe 10-100 for magnitude myself).
  - sir_kin 8y ago
    For more info on that 1000:1 ratio, see [1]. [1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem https://en.wikipedia.org/wiki/Quantum_threshold_theorem
- mirekrusin 8y ago
  Calculation on quantum state is already spread in time. Each time you calculate something you basically take snapshot of the state. Then you do it again. After many trials patterns emerge - that’s when you start reading your answer - which is always probabilistic.
wiz21c 8y ago
>>> qubits are highly unstable newbie question : are they naturally instable (so we won't fix that) or is it just because we don't master them well enough right now (and we'll fix them "soon") ?
- deepGem 8y ago
  It's the former. They can be made stable at super conducting temperatures but not completely. There will always be errors. From what I can understand you cant fully eliminate the errors. I donno may be some new superconducting temp might make them stable but that's a wild guess.

dzhiurgis 8y ago

A lot of things regarding chemistry and biology - finding catalysts for nitrate fertiliser production (uses 5% of worlds power), perhaps some catalysts in cement production (my idea), invention of new medicines, either due to better cell simulations or (my idea) faster protein folding.

aaavl2821 8y ago
Is the bottleneck preventing better cell simulations computational or lack of data / insufficient understanding of biology to inform a predictive model?
- thatcherc 8y ago
  My understanding as a physics undergrad is that we can write down the 'equations of motion' of molecular systems with Hamiltonians describing the energies and correlations of the electrons in a system, but they very quickly become intractably difficult to solve. You're trying to solve a very, very big eigenvalue problem. However, with the right kind of quantum computer or quantum simulator, you could construct a system of qubits that is described by the exact same Hamiltonian. That way, the quantum state of your qubits and your original system would behave in exactly the same way. Then, you just let the qubits evolve in time and read out the system's state at the end. Do that a bunch of times and you'll see an average picture of what the original system you're modelling (protein or something) would do. So to recap - we can get around the difficult compute bottleneck caused by the desire to perform high-fidelity physics simulations by creating a system that follows the same rules and which we can probe much more easily.
- BookmarkSaver 8y ago
  Not an expert, but my understanding is that while better knowledge/models of the biology might be useful, ultimately it's just a massive computational project to test out and optimize protein folding and such complex chemical behavior. The physics/chemistry and biology are understood well enough, there are just nearly countless paths to explore making it a huge problem.
  - 8y ago

rurban 8y ago

2048 would break current crypto, >20 would help solving most unsolvable NP hard problems.

sir_kin 8y ago
2018 LOGICAL qubits would break current crypto. But qubits decohere extremely fast, so you need error correcting schemes. Current estimates require 1000 - 10000 physical qubits per logical error corrected qubit. [1] https://en.wikipedia.org/wiki/Quantum_threshold_theorem https://en.wikipedia.org/wiki/Quantum_threshold_theorem
- rurban 8y ago
  No, no one cares about those HW problems. To break RSA keys you need 0 error correction. You only need >2000 entangled qbits, and they either produce a correct result or not. For other calculations you might need error correction, but this leads to nowhere with current technology. What the Chinese did was groundbreaking.