10 ms·

I’m a quantum dabbler so I’ll throw out an armchair reaction: this is a significant announcement. My memory is that 256 bit keys in non quantum resistant algos

I’m a quantum dabbler so I’ll throw out an armchair reaction: this is a significant announcement. My memory is that 256 bit keys in non quantum resistant algos need something like 2500 qubits or so; and by that I mean generally useful programmable qubits. To show a bit over 100 qubits with stability, meaning the information survives a while, long enough to be read, and general enough to run some benchmarks on is something many people thought might never come. There’s a sort of religious reaction people have to quantum computing: it breaks so many things that I think a lot of people just like to assume it won’t happen: too much in computing and data security will change -> let’s not worry about it. Combined with the slow pace of physical research progress (Schorrs algorithm for quantum factoring was mid 90s), and snake oil sales companies, it’s easy to ignore. Anyway seems like the clock might be ticking; AI and data security will be unalterably different if so. Worth spending a little time doing some long tail strategizing I’d say.

goatking 2y ago
How can I, a regular software engineer, learn about quantum computing without having to learn quantum theory? > Worth spending a little time doing some long tail strategizing I’d say any tips for starters?
- sshb 2y ago
  Might be worth checking out: https://quantum.country/ https://quantum.country/
- zitterbewegung 2y ago
  I recommend this book I studied it in Undergrad and I never took a quantum theory course. https://www.amazon.com/Quantum-Computing-Computer-Scientists-Yanofsky/dp/0521879965/ https://www.amazon.com/Quantum-Computing-Computer-Scientists...
  - raidicy 2y ago
    Are there any insights that you can give based off the info you've learned about quantum computation that you might not have been able to reach if you hadn't learned about it? From my __very__ shallow understanding, because all of the efficiency increases are in very specific areas, it might not be useful for the average computer science interested individual?
    - zitterbewegung 2y ago
      Nearly all of quantum computation is theoretical algorithms and the hard engineering problems haven't been solved. Most of the math though has a large amount of overlap of AI / ML and all of deep learning to the point that Quantum computers could be used as "ML accelerators" by using algorithms (this is called Quantum Machine learning) [1]. Quantum computing could be learned with a limited understanding of Quantum theory unless you are trying to engineer the hardware. https://en.wikipedia.org/wiki/Quantum_machine_learning https://en.wikipedia.org/wiki/Quantum_machine_learning
      - kvathupo 2y ago
        Possibly of interest, but I wrote a (hopefully approachable) report on quantum perceptrons a few years back [1]. Perhaps it's found elsewhere, but I was surprised by how, at least in this quantum algo's case, the basis of training was game theoretic not gradient descent! [1] - https://kvathupo.github.io/cs/quantum/457_Final_Report.pdf https://kvathupo.github.io/cs/quantum/457_Final_Report.pdf
- potsandpans 2y ago
  Start here: https://youtu.be/F_Riqjdh2oM https://youtu.be/F_Riqjdh2oM You don't need to know quantum theory necessarily, but you will need to know some maths. Specifically linear algebra. There are a few youtube courses on linear algebra For a casual set of video: - https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFit... For a more formal approach: - https://youtube.com/playlist?list=PL49CF3715CB9EF31D https://youtube.com/playlist?list=PL49CF3715CB9EF31D And the corresponding open courseware - https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/ https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010... Linear algebra done right comes highly recommended - https://linear.axler.net/ https://linear.axler.net/
  - RossBencina 2y ago
    +1 for 18-06 and Axler. Another, more concrete, option (not sure how much it will help with quantum theory) is Stephen Boyd's "Introduction to Applied Linear Algebra" available online here: https://web.stanford.edu/~boyd/vmls/ https://web.stanford.edu/~boyd/vmls/
  - pagekicker 2y ago
    Isn't there a Python library that abstracts most of it away with a couple of gigantic classes with incompatible dependencies?
- jvanderbot 2y ago
  There is a course mentioned in the article, but I'm not clear on how "theory" it is. https://coursera.org/learn/quantum-error-correction https://coursera.org/learn/quantum-error-correction
- carabiner 2y ago
  First learn about eigenvalues.
- billti 2y ago
  If you're a software engineer, then the Quantum Katas might fit your learning style. The exercises use Q#, which is quantum specific programming language. https://quantum.microsoft.com/en-us/tools/quantum-katas https://quantum.microsoft.com/en-us/tools/quantum-katas The first few lessons do cover complex numbers and linear algebra, so skip ahead if you want to get straight to the 'quantum' coding, but there's really no escaping the math if you really want to learn quantum. Disclaimer: I work in the Azure Quantum team on our Quantum Development Kit (https://github.com/microsoft/qsharp https://github.com/microsoft/qsharp) - including Q#, the Katas, and our VS Code extension. Happy to answer any other questions on it.
  - auto 2y ago
    Is there a reasonable pivot for someone well versed in the software engineering space to get in, or is it still the playground of relevant Ph.Ds and the like? I've been up and down the stack from firmware to the cloud, going on 14 years in the industry, have a Master's in CS, am the technical lead for a team, yada yada, but have been flirting with the idea of getting out of standard product development and back into the nitty gritty of the space I first pursued during undergrad.
    - almostgotcaught 2y ago
      > Is there a reasonable pivot for someone well versed in the software engineering space to get in, or is it still the playground of relevant Ph.Ds and the like? there's no such thing as a practical QC and there won't be for decades. this isn't a couple of years away - this is "maybe, possibly, pretty please, if we get lucky" 25-50 years away. find the above comment that alludes to "2019 estimates needing ~20 million physical qubits" and consider that this thing has 105 physical qubits. then skim the posted article and find this number > the key quantum computational resource — are now approaching 100 µs (microseconds) that's how long those 105 physical qubits stay coherent for. now ponder your career pivot. source: i dabbled during my PhD - took a couple of classes from Fred Chong, wrote a paper - it's all hype.
- kvathupo 2y ago
  The bar for entry is surprisingly low, you just need to brush up on intro abstract algebra. I recommend the following: 1. Kaye, LaFlamme, and Mosca - An Introduction to Quantum Computing 2. Nielsen and Chuang - Quantum Computation and Quantum Information (The Standard reference source) 3. Andrew Childs's notes here [1]. Closest to the state-of-the-art, at least circa ~3 years ago. [1] - https://www.cs.umd.edu/~amchilds/qa/ https://www.cs.umd.edu/~amchilds/qa/
- neoden 2y ago
  These lessons might be of help: https://youtu.be/3-c4xJa7Flk?si=krrpXMKh3X5ktrzT https://youtu.be/3-c4xJa7Flk?si=krrpXMKh3X5ktrzT
- currymj 2y ago
  specifically avoid resources written by and for physicists. the model of quantum mechanics, if you can afford to ignore any real-world physical system and just deal with abstract |0>, |1> qubits, is relatively easy. (this is really funny given how incredibly difficult actual quantum physics can be.) you have to learn basic linear algebra with complex numbers (can safely ignore anything really gnarly). then you learn how to express Boolean circuits in terms of different matrix multiplications, to capture classical computation in this model. This should be pretty easy if you have a software engineer's grasp of Boolean logic. Then you can learn basic ideas about entanglement, and a few of the weird quantum tricks that make algorithms like Shor and Grover search work. Shor's algorithm may be a little mathematically tough. realistically you probably will never need to know how to program a quantum computer even if they become practical and successful. applications are powerful but very limited. "What You Shouldn't Know About Quantum Computers" is a good non-mathematical read. https://arxiv.org/abs/2405.15838 https://arxiv.org/abs/2405.15838
- ajb 2y ago
  The simplest algorithm to understand is probably Grover's algorithm. Knowing that shows you how to get an sqrt(N) speedup on many classical algorithms. Then have a look at shor's algorithm which is the classic factoring algorithm. I would not worry about hardware at first. But if you are interested and like physics, the simplest to understand are linear optical quantum circuits. These use components which may be familiar from high school or undergraduate physics. The catch is that the space (and component count) is exponential in the number of qubits, hence the need for more exotic designs.
- cevi 2y ago
  I always recommend Watrous's lecture notes: https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.pdf https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.pdf I prefer his explanation to most other explanations because he starts, right away, with an analogy to ordinary probabilities. It's easy to understand how linear algebra is related to probability (a random combination of two outcomes is described by linearly combining them), so the fact that we represent random states by vectors is not surprising at all. His explanation of the Dirac bra-ket notation is also extremely well executed. My only quibble is that he doesn't introduce density matrices (which in my mind are the correct way to understand quantum states) until halfway through the notes.
- tsimionescu 2y ago
  If you want to learn about what theoretical quantum computers might be able to do faster than classical ones and what they might not, you can try to read about quantum complexity theory, or some of what Scott Aaronson puts out on his blog if you don't want to go that in depth. But the key thing to know about quantum computing is that it is all about the mathematical properties of quantum physics, such as the way complex probabilities work.
thrance 2y ago
The error rates given are still horrendous and nowhere near low enough for the Quantum Fourier Transform used by Shor's algorithm. Taking qubit connectivity into account, a single CX between 2 qubits that are 10 edges aways gives an error rate of 1.5%. Also, the more qubits you have/the more instructions are in your program, the faster the quantum state collapses. Exponentially so. Qubit connectivity is still ridiculously low (~3) and does not seem to be improving at all. About AI, what algorithm(s) do you think might have an edge over classical supercomputers in the next 30 years? I'm really curious, because to me it's all (quantum) snake oil.
- LeftHandPath 2y ago
  Re: AI, it's a long way off still. The big limitation to anything quantum is always going to be decoherence and t-time [0]. To do anything with ML, you'll need whole circuit (more complex than shor's) just to initialize the data on the quantum device; the algorithms to do this are complex (exponential) [1]. So, you have to run a very expensive data-initialization circuit, and only then can you start to run your ML circuit. All of this needs to be done within the machine's t-time limit. If you exceed that limit, then the measured state of a qubit will have more to do with outside-world interactions than interactions with your quantum gates. Google's willow chip has t-times of about 60-100mu.s. That's not an impressive figure -- in 2022, IBM announced their Eagle chip with t-times of around 400mu.s [2]. Google's angle here would be the error correction (EC). The following portion from Google's announcement seems most important: > With 105 qubits, Willow now has best-in-class performance across the two system benchmarks discussed above: quantum error correction and random circuit sampling. Such algorithmic benchmarks are the best way to measure overall chip performance. Other more specific performance metrics are also important; for example, our T1 times, which measure how long qubits can retain an excitation — the key quantum computational resource — are now approaching 100 µs (microseconds). This is an impressive ~5x improvement over our previous generation of chips. Again, as they lead with, their focus here is on error correction. I'm not sure how their results compare to competitors, but it sounds like they consider that to be the biggest win of the project. The RCS metric is interesting, but RCS has no (known) practical applications (though it is a common benchmark). Their T-times are an improvement over older Google chips, but not industry-leading. I'm curious if EC can mitigate the sub-par decoherence times. [0]: https://www.science.org/doi/abs/10.1126/science.270.5242.1633 https://www.science.org/doi/abs/10.1126/science.270.5242.163... [1]: https://dl.acm.org/doi/abs/10.5555/3511065.3511068 https://dl.acm.org/doi/abs/10.5555/3511065.3511068 [2]: https://www.ibm.com/quantum/blog/eagle-quantum-processor-performance https://www.ibm.com/quantum/blog/eagle-quantum-processor-per...
isoprophlex 2y ago
Data security okay. But AI? How will that change?
- adastra22 2y ago
  AI is essentially search. Quantum computers are really good at search.
  - sheeshkebab 2y ago
    Search of what?
    - roywiggins 2y ago
      Latent space? https://en.wikipedia.org/wiki/Latent_space https://en.wikipedia.org/wiki/Latent_space
    - adastra22 2y ago
      Anything. Everything. In domains where the search space is small enough to physically enumerate and store or evaluate every option, search is commonly understood as a process solved by simple algorithms. In domains where the search space is too large to physically realize or index, search becomes "intelligence." E.g. winning at Chess or Go (traditional AI domains) is searching through the space of possible game states to find a most-likely-to-win path. E.g. an LLM chat application is searching through possible responses to find one which best correlates with expected answer to the prompt. With Grover's algorithm, quantum computers let you find an answer in any disordered search space with O(sqrt(N)) operations instead of O(N). That's potentially applicable to many AI domains. But if you're so narrow minded as to only consider connectionist / neural network algorithms as "AI", then you may be interested to know that quantum linear algebra is a thing too: https://en.wikipedia.org/wiki/HHL_algorithm https://en.wikipedia.org/wiki/HHL_algorithm
      - cwillu 2y ago
        O(sqrt(N)) is easily dominated by the relative ease of constructing much bigger classical computers though.
JanisErdmanis 2y ago
The required number of qubits to execute Shor’s algorithm is way larger than 2500 qubits as the error ceiling for logical qubits must decrease exponentially with every logical qubit added to produce meaningful results. Hence, repeated applications of error correction or an increase in the surface code would be required. That would significantly blow up the number of physical qubits needed.
- adastra22 2y ago
  He’s quoting the number of logical qubits (which is 1024 IIRC, not 2500), after error correction. ETA: Wikipedia 2330 qubits, but I'm not sure it is citing the most recent work: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#cite_ref-42 https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#ci...
  - pclmulqdq 2y ago
    1024 is for RSA-1024, which is believed to be broken by classical means at this point. Everyone doing anything with RSA is on 4k or larger.
    - Vecr 2y ago
      They are? The short term recommendation is 3072, and I still see lots of 2048. Actually, it's mostly 2048.
    - deleted 2y ago
      [deleted]
    - wcoenen 2y ago
      > Everyone doing anything with RSA is on 4k or larger. The Let's Encrypt intermediate certificates R10 and R11 seem to be only 2048 bit.
      - pclmulqdq 2y ago
        A signature (not encryption) with short-term valid life is fine at 2048 still.
winwang 2y ago
Edit after skimming arxiv preprint[1]: Yeah, this is pretty huge. They achieved the result with surface codes, which are general ECCs. The repetition code was used to further probe quantum ECC floor. "Just POC" likely doesn't do it justice. (Original comment): Also quantum dabbler (coincidentally dabbled in bitflip quantum error correction research). Skimmed the post/research blog. I believe the key point is the scaling of error correction via repetition codes, would love someone else's viewpoint. Slightly concerning quote[2]: """ By running experiments with repetition codes and ignoring other error types, we achieve lower encoded error rates while employing many of the same error correction principles as the surface code. The repetition code acts as an advance scout for checking whether error correction will work all the way down to the near-perfect encoded error rates we’ll ultimately need. """ I'm getting the feeling that this is more about proof-of-concept, rather than near-practicality, but this is certainly one fantastic POC if true. [1]: https://arxiv.org/abs/2408.13687 https://arxiv.org/abs/2408.13687 [2]: https://research.google/blog/making-quantum-error-correction-work/ https://research.google/blog/making-quantum-error-correction... Relevant quote from preprint (end of section 1, sorry for copy-paste artifacts): """ In this work, we realize surface codes operating below threshold on two superconducting processors. Using a 72-qubit processor, we implement a distance-5 surface code operating with an integrated real-time decoder. In addition, using a 105-qubit processor with similar performance, we realize a distance-7 surface code. These processors demonstrate Λ > 2 up to distance-5 and distance7, respectively. Our distance-5 quantum memories are beyond break-even, with distance-7 preserving quantum information for more than twice as long as its best constituent physical qubit. To identify possible logical error f loors, we also implement high-distance repetition codes on the 72-qubit processor, with error rates that are dominated by correlated error events occurring once an hour. These errors, whose origins are not yet understood, set a current error floor of 10−10. Finally, we show that we can maintain below-threshold operation on the 72qubit processor even when decoding in real time, meeting the strict timing requirements imposed by the processor’s fast 1.1µs cycle duration. """
- echelon 2y ago
  Google could put themselves and everyone else out of business if the algorithms that underpin our ability to do e-commerce and financial transactions can be defeated. Goodbye not just to Bitcoin, but also Visa, Stripe, Amazon shopping, ...
deleted 2y ago
[deleted]
deleted 2y ago
[deleted]
bee_rider 2y ago
I think some element of it might be: Shor’s algorithm has been known of for 30 years, and hypothetically could be used to decrypt captured communications, right? So, retroactively I will have been dumb for not having switched to a quantum-resistant scheme. And, dumb in a way that a bunch of academic nerds have been pointing out for decades. That level of embarrassment is frankly difficult to face. And it would be devastating to the self-image of a bunch of “practical” security gurus. Therefore any progress must be an illusion. In the real world, the threats are predictable and mistakes don’t slowly snowball into a crisis. See also, infrastructure.
- adastra22 2y ago
  What would you switch to? There hasn’t been post quantum systems to use until very very recently.
- bawolff 2y ago
  All you encrypted communication from the 90s (SSL anyways) can probably be decrypted with classical means anyways. 90s SSL was pretty bad.
cherryteastain 2y ago
> AI and data security will be unalterably different if so Definitely agree with the latter, but do you have any sources on how quantum comphters make "AI" (i.e. matrix multiplication) faster?
- meta_x_ai 2y ago
  Exploring via Search can become O(1) instead of M^N
  - bawolff 2y ago
    That is definitely not true.
npalli 2y ago
> Worth spending a little time doing some long tail strategizing I’d say. Yup, like Bitcoin going to zero.
- drcode 2y ago
  eh, they will add a quantum-resistant signature scheme (already a well-understood thing) then people can transfer their funds to the new addresses before it is viable to crack the existing addresses
  - bangaladore 2y ago
    So the first company that can break bitcoin addresses using quantum computers gets a prize of how many billion(?) dollars by stealing all the non-migrated addresses. Is that a crime? Lots of forgotten keys in there.
    - webXL 2y ago
      A very interesting philosophical and moral can of worms you just opened there. Bitcoin is governed by the protocol, so if the protocol permits anyone who can sign a valid transaction involving a given UTXO to another address, then it technically isn't a "crime". Morally I'm not sure I'd be able to sleep well at night if I unilaterally took what I didn't exchange value for. As for the forgotten key case, I think the only way to prove you had the key at some point would need to involve the sender vouching for you and cryptographically proving they were the sender.
      - tsimionescu 2y ago
        Morally, there is no quandary: it's obviously morally wrong to take someone else's things, and knowing their private key changes nothing. Legally, the situation is the same: legal ownership is not in any way tied to the mechanism of how some system or another keeps track of ownership. Your BTC is yours via a contract, not because the BTC network says so. Of course, proving to a judge that someone else stole your BTC may be extremely hard, if not impossible. Saying "if the protocol permits anyone who can sign a valid transaction involving a given UTXO to another address, then it technically isn't a "crime"" is like saying "traditional banking is governed by a banker checking your identity, so if someone can convince the banker they are you, then it technically isn't a "crime"". The only thing that wouldn't be considered a crime, in both cases, is the system allowing the transaction to happen. That is, it's not a crime for the bank teller to give your money to someone else if they were legitimately fooled; and it's not a crime for the Bitcoin miners to give your money to someone else if that someone else impersonated your private key. But the person who fooled the bank teller /the miners is definitely committing a crime.
qnleigh 2y ago
You need to distinguish between "physical qubits" and "logical qubits." This paper creates a single "first-of-a-kind" logical qubit with about 100 physical qubits (using Surface Code quantum error correction). A paper from Google in 2019 estimates needing ~20 million physical qubits ("How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" - https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749), though recent advances probably brought this number down a bit. That's because to run Shor's algorithm at a useful scale, you need a few thousand very high quality logical qubits. So despite this significant progress, it's probably a still a while until RSA is put out of the job. That being said, quantum computers would be able to retroactively break any public keys that were stored, so there's a case to be made for switching to quantum-resistant cryptography (like lattice-based cryptography) sooner rather than later.
- rhubarbtree 2y ago
  This is correct. I worked in quantum research a little.
  - orliesaurus 2y ago
    any books for beginners that you recommend?
    - macrolime 2y ago
      https://quantum.country/qcvc https://quantum.country/qcvc
      - sebastialonso 2y ago
        This is an outstanding resource, thanks!
  - ozzsama 2y ago
    Dear rhubarbtree, I'm very sorry to admit it but I'm too lazy to read the entire discussion in this thread. Could you please tell me, a mere mortal, at which point the humanity should start worrying about the security of asymmetric encryption in the brave new world of quantum computing?
r33b33 2y ago
> Worth spending a little time doing some long tail strategizing I’d say. What do you mean by this?
- unethical_ban 2y ago
  The only thing I know or understand about quantum computing is its ability to "crack" traditional encryption algorithms. So the commenter is saying that Cybersecurity needs to be planning for a near-world where traditional cryptography, including lots of existing data at rest, is suddenly as insecure as plaintext.
- tsimionescu 2y ago
  "long tail" typically refers to the tail of a normal distribution - basically it's a sciencey, but common, way of saying "very unlikely event". So, the OP was saying that it's worth spending some time strategizing about the unlikely event that a practical RSA-breaking QC appears in the near future, even though it's still a "long tail" (very unlikely) event. Honestly, there's not that much to discuss on this though. The only things you can do from this strategizing is to consider even encrypted data as not safe to store, unless you're using quantum resistant encryption such as AES; and to budget time for switching to PQC as it becomes available.
sizzle 2y ago
How long until this can derive a private key from its public key in the cryptocurrency space? Is this an existential threat to crypto?
- bawolff 2y ago
  Long enough you don't need to panic or worry. Short enough that its reasonable to start r&d efforts on post quantum crypto.
  - sizzle 2y ago
    Is there a way to fork and add a quantum-proof encryption layer on the existing cryptocurrency paradigm i.e. Bitcoin 2.0?
    - bawolff 2y ago
      You could replace ECDSA with a post quantum algorithm. Keep in mind that many crypto primitives are safe, so there are large parts of bitcoin where you don't have to do anything. Digital signatures is going to be where the main problem is for bitcoin. But thinks like the hash algorithm should be fine (at most quantum gives a square root speed up for hashing, which isn't enough to be really concerning). One thing that might be problematic for a blockchain where everything has to go on the blockchain forever is that some post quantum schemes have really large signatures or key sizes. I'm not that familiar with the details of bitcoin, but i had the impression that p2pkh is more secure against quantum computers. [I should emphasize, im not a cryptographer and only somewhat familiar with bitcoin]
- ryankshaw 2y ago
  I had the same question and this article was really helpful in explaining the threat models https://www.deloitte.com/nl/en/services/risk-advisory/perspectives/quantum-computers-and-the-bitcoin-blockchain.html https://www.deloitte.com/nl/en/services/risk-advisory/perspe...
- valval 2y ago
  This is the same as climate change. Something might happen sometime in the future.
beams_of_light 2y ago
https://en.wikipedia.org/wiki/BGP_hijacking#Public_incidents https://en.wikipedia.org/wiki/BGP_hijacking#Public_incidents A long-term tactic of our adversaries is to capture network traffic for later decryption. The secrets in the mass of packets China assumedly has in storage, waiting for quantum tech, is a treasure trove that could lead to crucial state, corporate, and financial secrets being used against us or made public. AI being able to leverage quantum processing power is a threat we can't even fathom right now. Our world is going to change.
inasio 2y ago
They showed a logical qubit that can last entangled for an hour, but to do that they had to combine their hundred or so physical qubits into a single one, so in some sense they have, right now, a single (logical) qubit
weatherlite 2y ago
> AI and data security will be unalterably different if so So what are the implications if so ?

goatking 2y ago

How can I, a regular software engineer, learn about quantum computing without having to learn quantum theory? > Worth spending a little time doing some long tail strategizing I’d say any tips for starters?

sshb 2y ago
Might be worth checking out: https://quantum.country/ https://quantum.country/
zitterbewegung 2y ago
I recommend this book I studied it in Undergrad and I never took a quantum theory course. https://www.amazon.com/Quantum-Computing-Computer-Scientists-Yanofsky/dp/0521879965/ https://www.amazon.com/Quantum-Computing-Computer-Scientists...
- raidicy 2y ago
  Are there any insights that you can give based off the info you've learned about quantum computation that you might not have been able to reach if you hadn't learned about it? From my __very__ shallow understanding, because all of the efficiency increases are in very specific areas, it might not be useful for the average computer science interested individual?
  - zitterbewegung 2y ago
    Nearly all of quantum computation is theoretical algorithms and the hard engineering problems haven't been solved. Most of the math though has a large amount of overlap of AI / ML and all of deep learning to the point that Quantum computers could be used as "ML accelerators" by using algorithms (this is called Quantum Machine learning) [1]. Quantum computing could be learned with a limited understanding of Quantum theory unless you are trying to engineer the hardware. https://en.wikipedia.org/wiki/Quantum_machine_learning https://en.wikipedia.org/wiki/Quantum_machine_learning
    - kvathupo 2y ago
      Possibly of interest, but I wrote a (hopefully approachable) report on quantum perceptrons a few years back [1]. Perhaps it's found elsewhere, but I was surprised by how, at least in this quantum algo's case, the basis of training was game theoretic not gradient descent! [1] - https://kvathupo.github.io/cs/quantum/457_Final_Report.pdf https://kvathupo.github.io/cs/quantum/457_Final_Report.pdf
potsandpans 2y ago
Start here: https://youtu.be/F_Riqjdh2oM https://youtu.be/F_Riqjdh2oM You don't need to know quantum theory necessarily, but you will need to know some maths. Specifically linear algebra. There are a few youtube courses on linear algebra For a casual set of video: - https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab https://youtube.com/playlist?list=PLZHQObOWTQDPD3MizzM2xVFit... For a more formal approach: - https://youtube.com/playlist?list=PL49CF3715CB9EF31D https://youtube.com/playlist?list=PL49CF3715CB9EF31D And the corresponding open courseware - https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010/ https://ocw.mit.edu/courses/18-06-linear-algebra-spring-2010... Linear algebra done right comes highly recommended - https://linear.axler.net/ https://linear.axler.net/
- RossBencina 2y ago
  +1 for 18-06 and Axler. Another, more concrete, option (not sure how much it will help with quantum theory) is Stephen Boyd's "Introduction to Applied Linear Algebra" available online here: https://web.stanford.edu/~boyd/vmls/ https://web.stanford.edu/~boyd/vmls/
- pagekicker 2y ago
  Isn't there a Python library that abstracts most of it away with a couple of gigantic classes with incompatible dependencies?
jvanderbot 2y ago
There is a course mentioned in the article, but I'm not clear on how "theory" it is. https://coursera.org/learn/quantum-error-correction https://coursera.org/learn/quantum-error-correction
carabiner 2y ago
First learn about eigenvalues.
billti 2y ago
If you're a software engineer, then the Quantum Katas might fit your learning style. The exercises use Q#, which is quantum specific programming language. https://quantum.microsoft.com/en-us/tools/quantum-katas https://quantum.microsoft.com/en-us/tools/quantum-katas The first few lessons do cover complex numbers and linear algebra, so skip ahead if you want to get straight to the 'quantum' coding, but there's really no escaping the math if you really want to learn quantum. Disclaimer: I work in the Azure Quantum team on our Quantum Development Kit (https://github.com/microsoft/qsharp https://github.com/microsoft/qsharp) - including Q#, the Katas, and our VS Code extension. Happy to answer any other questions on it.
- auto 2y ago
  Is there a reasonable pivot for someone well versed in the software engineering space to get in, or is it still the playground of relevant Ph.Ds and the like? I've been up and down the stack from firmware to the cloud, going on 14 years in the industry, have a Master's in CS, am the technical lead for a team, yada yada, but have been flirting with the idea of getting out of standard product development and back into the nitty gritty of the space I first pursued during undergrad.
  - almostgotcaught 2y ago
    > Is there a reasonable pivot for someone well versed in the software engineering space to get in, or is it still the playground of relevant Ph.Ds and the like? there's no such thing as a practical QC and there won't be for decades. this isn't a couple of years away - this is "maybe, possibly, pretty please, if we get lucky" 25-50 years away. find the above comment that alludes to "2019 estimates needing ~20 million physical qubits" and consider that this thing has 105 physical qubits. then skim the posted article and find this number > the key quantum computational resource — are now approaching 100 µs (microseconds) that's how long those 105 physical qubits stay coherent for. now ponder your career pivot. source: i dabbled during my PhD - took a couple of classes from Fred Chong, wrote a paper - it's all hype.
kvathupo 2y ago
The bar for entry is surprisingly low, you just need to brush up on intro abstract algebra. I recommend the following: 1. Kaye, LaFlamme, and Mosca - An Introduction to Quantum Computing 2. Nielsen and Chuang - Quantum Computation and Quantum Information (The Standard reference source) 3. Andrew Childs's notes here [1]. Closest to the state-of-the-art, at least circa ~3 years ago. [1] - https://www.cs.umd.edu/~amchilds/qa/ https://www.cs.umd.edu/~amchilds/qa/
neoden 2y ago
These lessons might be of help: https://youtu.be/3-c4xJa7Flk?si=krrpXMKh3X5ktrzT https://youtu.be/3-c4xJa7Flk?si=krrpXMKh3X5ktrzT
currymj 2y ago
specifically avoid resources written by and for physicists. the model of quantum mechanics, if you can afford to ignore any real-world physical system and just deal with abstract |0>, |1> qubits, is relatively easy. (this is really funny given how incredibly difficult actual quantum physics can be.) you have to learn basic linear algebra with complex numbers (can safely ignore anything really gnarly). then you learn how to express Boolean circuits in terms of different matrix multiplications, to capture classical computation in this model. This should be pretty easy if you have a software engineer's grasp of Boolean logic. Then you can learn basic ideas about entanglement, and a few of the weird quantum tricks that make algorithms like Shor and Grover search work. Shor's algorithm may be a little mathematically tough. realistically you probably will never need to know how to program a quantum computer even if they become practical and successful. applications are powerful but very limited. "What You Shouldn't Know About Quantum Computers" is a good non-mathematical read. https://arxiv.org/abs/2405.15838 https://arxiv.org/abs/2405.15838
ajb 2y ago
The simplest algorithm to understand is probably Grover's algorithm. Knowing that shows you how to get an sqrt(N) speedup on many classical algorithms. Then have a look at shor's algorithm which is the classic factoring algorithm. I would not worry about hardware at first. But if you are interested and like physics, the simplest to understand are linear optical quantum circuits. These use components which may be familiar from high school or undergraduate physics. The catch is that the space (and component count) is exponential in the number of qubits, hence the need for more exotic designs.
cevi 2y ago
I always recommend Watrous's lecture notes: https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.pdf https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.pdf I prefer his explanation to most other explanations because he starts, right away, with an analogy to ordinary probabilities. It's easy to understand how linear algebra is related to probability (a random combination of two outcomes is described by linearly combining them), so the fact that we represent random states by vectors is not surprising at all. His explanation of the Dirac bra-ket notation is also extremely well executed. My only quibble is that he doesn't introduce density matrices (which in my mind are the correct way to understand quantum states) until halfway through the notes.
tsimionescu 2y ago
If you want to learn about what theoretical quantum computers might be able to do faster than classical ones and what they might not, you can try to read about quantum complexity theory, or some of what Scott Aaronson puts out on his blog if you don't want to go that in depth. But the key thing to know about quantum computing is that it is all about the mathematical properties of quantum physics, such as the way complex probabilities work.

thrance 2y ago

The error rates given are still horrendous and nowhere near low enough for the Quantum Fourier Transform used by Shor's algorithm. Taking qubit connectivity into account, a single CX between 2 qubits that are 10 edges aways gives an error rate of 1.5%. Also, the more qubits you have/the more instructions are in your program, the faster the quantum state collapses. Exponentially so. Qubit connectivity is still ridiculously low (~3) and does not seem to be improving at all. About AI, what algorithm(s) do you think might have an edge over classical supercomputers in the next 30 years? I'm really curious, because to me it's all (quantum) snake oil.

LeftHandPath 2y ago
Re: AI, it's a long way off still. The big limitation to anything quantum is always going to be decoherence and t-time [0]. To do anything with ML, you'll need whole circuit (more complex than shor's) just to initialize the data on the quantum device; the algorithms to do this are complex (exponential) [1]. So, you have to run a very expensive data-initialization circuit, and only then can you start to run your ML circuit. All of this needs to be done within the machine's t-time limit. If you exceed that limit, then the measured state of a qubit will have more to do with outside-world interactions than interactions with your quantum gates. Google's willow chip has t-times of about 60-100mu.s. That's not an impressive figure -- in 2022, IBM announced their Eagle chip with t-times of around 400mu.s [2]. Google's angle here would be the error correction (EC). The following portion from Google's announcement seems most important: > With 105 qubits, Willow now has best-in-class performance across the two system benchmarks discussed above: quantum error correction and random circuit sampling. Such algorithmic benchmarks are the best way to measure overall chip performance. Other more specific performance metrics are also important; for example, our T1 times, which measure how long qubits can retain an excitation — the key quantum computational resource — are now approaching 100 µs (microseconds). This is an impressive ~5x improvement over our previous generation of chips. Again, as they lead with, their focus here is on error correction. I'm not sure how their results compare to competitors, but it sounds like they consider that to be the biggest win of the project. The RCS metric is interesting, but RCS has no (known) practical applications (though it is a common benchmark). Their T-times are an improvement over older Google chips, but not industry-leading. I'm curious if EC can mitigate the sub-par decoherence times. [0]: https://www.science.org/doi/abs/10.1126/science.270.5242.1633 https://www.science.org/doi/abs/10.1126/science.270.5242.163... [1]: https://dl.acm.org/doi/abs/10.5555/3511065.3511068 https://dl.acm.org/doi/abs/10.5555/3511065.3511068 [2]: https://www.ibm.com/quantum/blog/eagle-quantum-processor-performance https://www.ibm.com/quantum/blog/eagle-quantum-processor-per...

isoprophlex 2y ago

Data security okay. But AI? How will that change?

adastra22 2y ago
AI is essentially search. Quantum computers are really good at search.
- sheeshkebab 2y ago
  Search of what?
  - roywiggins 2y ago
    Latent space? https://en.wikipedia.org/wiki/Latent_space https://en.wikipedia.org/wiki/Latent_space
  - adastra22 2y ago
    Anything. Everything. In domains where the search space is small enough to physically enumerate and store or evaluate every option, search is commonly understood as a process solved by simple algorithms. In domains where the search space is too large to physically realize or index, search becomes "intelligence." E.g. winning at Chess or Go (traditional AI domains) is searching through the space of possible game states to find a most-likely-to-win path. E.g. an LLM chat application is searching through possible responses to find one which best correlates with expected answer to the prompt. With Grover's algorithm, quantum computers let you find an answer in any disordered search space with O(sqrt(N)) operations instead of O(N). That's potentially applicable to many AI domains. But if you're so narrow minded as to only consider connectionist / neural network algorithms as "AI", then you may be interested to know that quantum linear algebra is a thing too: https://en.wikipedia.org/wiki/HHL_algorithm https://en.wikipedia.org/wiki/HHL_algorithm
    - cwillu 2y ago
      O(sqrt(N)) is easily dominated by the relative ease of constructing much bigger classical computers though.

JanisErdmanis 2y ago

The required number of qubits to execute Shor’s algorithm is way larger than 2500 qubits as the error ceiling for logical qubits must decrease exponentially with every logical qubit added to produce meaningful results. Hence, repeated applications of error correction or an increase in the surface code would be required. That would significantly blow up the number of physical qubits needed.

adastra22 2y ago
He’s quoting the number of logical qubits (which is 1024 IIRC, not 2500), after error correction. ETA: Wikipedia 2330 qubits, but I'm not sure it is citing the most recent work: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#cite_ref-42 https://en.wikipedia.org/wiki/Elliptic-curve_cryptography#ci...
- pclmulqdq 2y ago
  1024 is for RSA-1024, which is believed to be broken by classical means at this point. Everyone doing anything with RSA is on 4k or larger.
  - Vecr 2y ago
    They are? The short term recommendation is 3072, and I still see lots of 2048. Actually, it's mostly 2048.
  - deleted 2y ago
    [deleted]
  - wcoenen 2y ago
    > Everyone doing anything with RSA is on 4k or larger. The Let's Encrypt intermediate certificates R10 and R11 seem to be only 2048 bit.
    - pclmulqdq 2y ago
      A signature (not encryption) with short-term valid life is fine at 2048 still.

winwang 2y ago

Edit after skimming arxiv preprint[1]: Yeah, this is pretty huge. They achieved the result with surface codes, which are general ECCs. The repetition code was used to further probe quantum ECC floor. "Just POC" likely doesn't do it justice. (Original comment): Also quantum dabbler (coincidentally dabbled in bitflip quantum error correction research). Skimmed the post/research blog. I believe the key point is the scaling of error correction via repetition codes, would love someone else's viewpoint. Slightly concerning quote[2]: """ By running experiments with repetition codes and ignoring other error types, we achieve lower encoded error rates while employing many of the same error correction principles as the surface code. The repetition code acts as an advance scout for checking whether error correction will work all the way down to the near-perfect encoded error rates we’ll ultimately need. """ I'm getting the feeling that this is more about proof-of-concept, rather than near-practicality, but this is certainly one fantastic POC if true. [1]: https://arxiv.org/abs/2408.13687 https://arxiv.org/abs/2408.13687 [2]: https://research.google/blog/making-quantum-error-correction-work/ https://research.google/blog/making-quantum-error-correction... Relevant quote from preprint (end of section 1, sorry for copy-paste artifacts): """ In this work, we realize surface codes operating below threshold on two superconducting processors. Using a 72-qubit processor, we implement a distance-5 surface code operating with an integrated real-time decoder. In addition, using a 105-qubit processor with similar performance, we realize a distance-7 surface code. These processors demonstrate Λ > 2 up to distance-5 and distance7, respectively. Our distance-5 quantum memories are beyond break-even, with distance-7 preserving quantum information for more than twice as long as its best constituent physical qubit. To identify possible logical error f loors, we also implement high-distance repetition codes on the 72-qubit processor, with error rates that are dominated by correlated error events occurring once an hour. These errors, whose origins are not yet understood, set a current error floor of 10−10. Finally, we show that we can maintain below-threshold operation on the 72qubit processor even when decoding in real time, meeting the strict timing requirements imposed by the processor’s fast 1.1µs cycle duration. """

echelon 2y ago
Google could put themselves and everyone else out of business if the algorithms that underpin our ability to do e-commerce and financial transactions can be defeated. Goodbye not just to Bitcoin, but also Visa, Stripe, Amazon shopping, ...

deleted 2y ago

[deleted]

deleted 2y ago

[deleted]

bee_rider 2y ago

I think some element of it might be: Shor’s algorithm has been known of for 30 years, and hypothetically could be used to decrypt captured communications, right? So, retroactively I will have been dumb for not having switched to a quantum-resistant scheme. And, dumb in a way that a bunch of academic nerds have been pointing out for decades. That level of embarrassment is frankly difficult to face. And it would be devastating to the self-image of a bunch of “practical” security gurus. Therefore any progress must be an illusion. In the real world, the threats are predictable and mistakes don’t slowly snowball into a crisis. See also, infrastructure.

adastra22 2y ago
What would you switch to? There hasn’t been post quantum systems to use until very very recently.
bawolff 2y ago
All you encrypted communication from the 90s (SSL anyways) can probably be decrypted with classical means anyways. 90s SSL was pretty bad.

cherryteastain 2y ago

> AI and data security will be unalterably different if so Definitely agree with the latter, but do you have any sources on how quantum comphters make "AI" (i.e. matrix multiplication) faster?

meta_x_ai 2y ago
Exploring via Search can become O(1) instead of M^N
- bawolff 2y ago
  That is definitely not true.

npalli 2y ago

> Worth spending a little time doing some long tail strategizing I’d say. Yup, like Bitcoin going to zero.

drcode 2y ago
eh, they will add a quantum-resistant signature scheme (already a well-understood thing) then people can transfer their funds to the new addresses before it is viable to crack the existing addresses
- bangaladore 2y ago
  So the first company that can break bitcoin addresses using quantum computers gets a prize of how many billion(?) dollars by stealing all the non-migrated addresses. Is that a crime? Lots of forgotten keys in there.
  - webXL 2y ago
    A very interesting philosophical and moral can of worms you just opened there. Bitcoin is governed by the protocol, so if the protocol permits anyone who can sign a valid transaction involving a given UTXO to another address, then it technically isn't a "crime". Morally I'm not sure I'd be able to sleep well at night if I unilaterally took what I didn't exchange value for. As for the forgotten key case, I think the only way to prove you had the key at some point would need to involve the sender vouching for you and cryptographically proving they were the sender.
    - tsimionescu 2y ago
      Morally, there is no quandary: it's obviously morally wrong to take someone else's things, and knowing their private key changes nothing. Legally, the situation is the same: legal ownership is not in any way tied to the mechanism of how some system or another keeps track of ownership. Your BTC is yours via a contract, not because the BTC network says so. Of course, proving to a judge that someone else stole your BTC may be extremely hard, if not impossible. Saying "if the protocol permits anyone who can sign a valid transaction involving a given UTXO to another address, then it technically isn't a "crime"" is like saying "traditional banking is governed by a banker checking your identity, so if someone can convince the banker they are you, then it technically isn't a "crime"". The only thing that wouldn't be considered a crime, in both cases, is the system allowing the transaction to happen. That is, it's not a crime for the bank teller to give your money to someone else if they were legitimately fooled; and it's not a crime for the Bitcoin miners to give your money to someone else if that someone else impersonated your private key. But the person who fooled the bank teller /the miners is definitely committing a crime.

qnleigh 2y ago

You need to distinguish between "physical qubits" and "logical qubits." This paper creates a single "first-of-a-kind" logical qubit with about 100 physical qubits (using Surface Code quantum error correction). A paper from Google in 2019 estimates needing ~20 million physical qubits ("How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" - https://arxiv.org/abs/1905.09749 https://arxiv.org/abs/1905.09749), though recent advances probably brought this number down a bit. That's because to run Shor's algorithm at a useful scale, you need a few thousand very high quality logical qubits. So despite this significant progress, it's probably a still a while until RSA is put out of the job. That being said, quantum computers would be able to retroactively break any public keys that were stored, so there's a case to be made for switching to quantum-resistant cryptography (like lattice-based cryptography) sooner rather than later.

rhubarbtree 2y ago
This is correct. I worked in quantum research a little.
- orliesaurus 2y ago
  any books for beginners that you recommend?
  - macrolime 2y ago
    https://quantum.country/qcvc https://quantum.country/qcvc
    - sebastialonso 2y ago
      This is an outstanding resource, thanks!
- ozzsama 2y ago
  Dear rhubarbtree, I'm very sorry to admit it but I'm too lazy to read the entire discussion in this thread. Could you please tell me, a mere mortal, at which point the humanity should start worrying about the security of asymmetric encryption in the brave new world of quantum computing?

r33b33 2y ago

> Worth spending a little time doing some long tail strategizing I’d say. What do you mean by this?

unethical_ban 2y ago
The only thing I know or understand about quantum computing is its ability to "crack" traditional encryption algorithms. So the commenter is saying that Cybersecurity needs to be planning for a near-world where traditional cryptography, including lots of existing data at rest, is suddenly as insecure as plaintext.
tsimionescu 2y ago
"long tail" typically refers to the tail of a normal distribution - basically it's a sciencey, but common, way of saying "very unlikely event". So, the OP was saying that it's worth spending some time strategizing about the unlikely event that a practical RSA-breaking QC appears in the near future, even though it's still a "long tail" (very unlikely) event. Honestly, there's not that much to discuss on this though. The only things you can do from this strategizing is to consider even encrypted data as not safe to store, unless you're using quantum resistant encryption such as AES; and to budget time for switching to PQC as it becomes available.

sizzle 2y ago

How long until this can derive a private key from its public key in the cryptocurrency space? Is this an existential threat to crypto?

bawolff 2y ago
Long enough you don't need to panic or worry. Short enough that its reasonable to start r&d efforts on post quantum crypto.
- sizzle 2y ago
  Is there a way to fork and add a quantum-proof encryption layer on the existing cryptocurrency paradigm i.e. Bitcoin 2.0?
  - bawolff 2y ago
    You could replace ECDSA with a post quantum algorithm. Keep in mind that many crypto primitives are safe, so there are large parts of bitcoin where you don't have to do anything. Digital signatures is going to be where the main problem is for bitcoin. But thinks like the hash algorithm should be fine (at most quantum gives a square root speed up for hashing, which isn't enough to be really concerning). One thing that might be problematic for a blockchain where everything has to go on the blockchain forever is that some post quantum schemes have really large signatures or key sizes. I'm not that familiar with the details of bitcoin, but i had the impression that p2pkh is more secure against quantum computers. [I should emphasize, im not a cryptographer and only somewhat familiar with bitcoin]
ryankshaw 2y ago
I had the same question and this article was really helpful in explaining the threat models https://www.deloitte.com/nl/en/services/risk-advisory/perspectives/quantum-computers-and-the-bitcoin-blockchain.html https://www.deloitte.com/nl/en/services/risk-advisory/perspe...
valval 2y ago
This is the same as climate change. Something might happen sometime in the future.

beams_of_light 2y ago

https://en.wikipedia.org/wiki/BGP_hijacking#Public_incidents https://en.wikipedia.org/wiki/BGP_hijacking#Public_incidents A long-term tactic of our adversaries is to capture network traffic for later decryption. The secrets in the mass of packets China assumedly has in storage, waiting for quantum tech, is a treasure trove that could lead to crucial state, corporate, and financial secrets being used against us or made public. AI being able to leverage quantum processing power is a threat we can't even fathom right now. Our world is going to change.

inasio 2y ago

They showed a logical qubit that can last entangled for an hour, but to do that they had to combine their hundred or so physical qubits into a single one, so in some sense they have, right now, a single (logical) qubit

weatherlite 2y ago

> AI and data security will be unalterably different if so So what are the implications if so ?