№ 125 · computing

Qubits: what they do, and what a quantum computer still cannot

A reader asked what a qubit actually does, and what a quantum computer still cannot do. The short answer: a qubit carries two numbers, not one bit, and a quantum program steers those numbers so that wrong answers cancel and the right one adds up. That works spectacularly for a few problems and barely helps most others. No quantum computer has broken a code anyone uses, and in a 2024 survey the largest number honestly factored with Shor's algorithm on real hardware was 35.

What a qubit holds

An ordinary bit is 0 or 1. A qubit is described by two numbers called amplitudes, one attached to 0 and one to 1. When you measure it you never see the amplitudes: you get a plain 0 or 1, and the chance of each is the square of the size of its amplitude. Amplitudes can be negative (in general they are complex numbers), and that turns out to be the whole point.

The bookkeeping grows fast. Peter Shor's factoring paper spells it out: describing n ordinary bits takes n bits, but describing n qubits takes one amplitude for every one of the 2n possible bit patterns. Fifty qubits need about a million billion numbers. That is why simulating a quantum machine on an ordinary one gets out of hand so quickly.

The common slogan is that a quantum computer "tries every answer at once". That alone does not help, because a measurement hands you one pattern, picked at random by those squared amplitudes. Read a machine holding every answer equally and you get a random guess. The work is in making the useful answer likely before you look.

Interference is the trick

Because amplitudes carry signs, two paths to the same outcome can cancel or add, like ripples on water. A quantum algorithm is a sequence of steps arranged so that the amplitudes of wrong answers cancel and the right one grows. Lov Grover's 1996 search algorithm is the cleanest example, and it is what the figure below runs. Start with every one of N items equally likely. One step flips the sign of the item you want, which a checking circuit can do without anyone knowing in advance which item that is. A second step reflects every amplitude about their average. The flipped item sits far below the average, so it lands far above it. Repeat, and after about 0.785 times the square root of N rounds the item you want is close to certain. Go further and it overshoots and falls again.

Interactive Pick how many items to search, then press the two steps in turn (or tab to a button and press Enter). Watch the one item you want grow while the others shrink, and see where it peaks.

16
rounds done0
chance a look finds it6.25%
same number of plain checks0%

Every item starts equally likely: a look now is a 1-in-16 guess. Press "check" to flip the sign of the item you want.

Our own drawing of Grover's search (Grover 1996), not a figure from any source. Each bar is one item's amplitude; the chance of finding an item when you look is the square of its bar. The checking step flips the sign of the wanted item only; the second step reflects every amplitude about the dashed average. All numbers are computed exactly for a perfect, noise-free machine with one wanted item. The best number of rounds is the one that gives the highest chance, found by running the same arithmetic; it comes out close to π/4 × √N, about 0.785√N. "Plain checks" is an ordinary search that has tested that many different items, one per round. Above 64 items only 64 bars are drawn: the red one and 63 of the others, which all stay identical.

That is a real speedup, but only a square root. Searching a million items takes about 785 rounds instead of up to a million checks. Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved in 1997 that for a search where the only thing you can do is check a candidate, no quantum method does better than that square root.

Where the big speedups are

A few problems have structure that interference can exploit far better. Shor showed in 1994 that a quantum computer could factor a whole number in a number of steps that grows only polynomially with its digits; the best known ordinary methods take far longer. The same paper breaks discrete logarithms, so the codes at risk are RSA, which rests on factoring, and the Diffie-Hellman and elliptic-curve methods used to agree keys and sign messages. NIST lists all of them as quantum-vulnerable. The other natural fit is simulating molecules and materials, which are themselves quantum systems: that 2n bookkeeping is the problem, and a quantum machine carries it natively.

What it still cannot do

It is not a faster computer for everything. John Preskill, who named today's noisy machines, wrote that physicists do not expect a quantum computer to solve the hard cases of problems like the travelling salesman efficiently; for those, the modest speedup on brute search is about what is on offer. Most everyday software, from spreadsheets to games, gains nothing.

It cannot yet run Shor's algorithm at any useful size. A 2024 survey by Dennis Willsch and colleagues found that the largest numbers factored honestly with Shor's algorithm on a real quantum computer were no bigger than 35. Many claims of larger ones, they note, rest on shortcuts that make the experiment no better than a coin flip.

The reason is noise. Qubits lose their amplitudes to the slightest disturbance, so long calculations need error correction: many physical qubits shared to hold one more reliable "logical" qubit. That only pays off if the hardware is already good enough. In 2024 Google showed it was: on its Willow chip, each step up in the size of a protected qubit cut its error rate by about half, down to 0.143% per cycle in the largest, built from 101 physical qubits. In 2025 the same chip ran a measurement of quantum chaos on 65 qubits that Google estimates would take the Frontier supercomputer about 13,000 times longer. It is a physics benchmark, not a commercial task.

How close the code-breakers are

What has moved fastest is the estimate of what breaking a code would take. In 2019 Craig Gidney and Martin Ekerå put RSA-2048 at 20 million noisy qubits. In 2025 Gidney brought it under a million, running for under a week, assuming qubits that err 0.1% of the time. In 2026 Madelyn Cain, Preskill and colleagues argued that a machine of movable neutral atoms could run Shor's algorithm at code-breaking sizes with as few as about 10,000 qubits, if slowly; their faster design for RSA-2048 uses about 102,000 qubits and some 97 days. These are designs on paper. The hardware they cite so far: arrays holding more than 6,000 good atoms, fault-tolerant operations below the error threshold, and computation on arrays of hundreds of qubits.

The replacement is already under way, because moving the world's software takes years. In August 2024 the US National Institute of Standards and Technology (NIST) approved its first three quantum-resistant standards and urged administrators to start switching at once. Its draft transition plan proposes that the vulnerable public-key methods be disallowed after 2035, with their weaker settings deprecated after 2030.

In one breath

A qubit holds amplitudes that can cancel, and a quantum algorithm arranges the cancelling so the right answer is likely when you look. That buys a square root on plain search, much more on factoring and on simulating nature, and nothing on most other work. Error correction now works in small, and code-breaking estimates keep shrinking, but no machine has come close to breaking a real key.

Where this comes from

  1. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer linked only, not reproduced
    Peter W. Shor (AT&T Research) · arXiv:quant-ph/9508027 · 1995
    arxiv.org/abs/quant-ph/9508027
  2. A fast quantum mechanical algorithm for database search linked only, not reproduced
    Lov K. Grover (Bell Labs, Murray Hill NJ) · arXiv:quant-ph/9605043 · 1996
    arxiv.org/abs/quant-ph/9605043
  3. Strengths and Weaknesses of Quantum Computing linked only, not reproduced
    Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani · arXiv:quant-ph/9701001 · 1997
    arxiv.org/abs/quant-ph/9701001
  4. Quantum Computing in the NISQ era and beyond reuse permitted with attribution
    John Preskill · arXiv:1801.00862 · 2018
    arxiv.org/abs/1801.00862
  5. The State of Factoring on Quantum Computers linked only, not reproduced
    Dennis Willsch, Philipp Hanussek, Georg Hoever, Madita Willsch, Fengping Jin, Hans De Raedt, Kristel Michielsen · arXiv:2410.14397 · 2024
    arxiv.org/abs/2410.14397
  6. Quantum error correction below the surface code threshold reuse permitted with attribution
    Rajeev Acharya, Laleh Aghababaie-Beni, Igor Aleiner, Trond I. Andersen, Markus Ansmann, Frank Arute, Kunal Arya, Abraham Asfaw, Nikita Astrakhantsev, Juan Atalaya, Ryan Babbush, Dave Bacon, Brian Ballard, Joseph C. Bardin, Johannes Bausch, Andreas Bengtsson, Alexander Bilmes, Sam Blackwell, Sergio Boixo, Gina Bortoli, Alexandre Bourassa, Jenna Bovaird, Leon Brill, Michael Broughton, David A. Browne, Brett Buchea, Bob B. Buckley, David A. Buell, Tim Burger, Brian Burkett, Nicholas Bushnell, Anthony Cabrera, Juan Campero, Hung-Shen Chang, Yu Chen, Zijun Chen, Ben Chiaro, Desmond Chik, Charina Chou, Jahan Claes, Agnetta Y. Cleland, Josh Cogan, Roberto Collins, Paul Conner, William Courtney, Alexander L. Crook, Ben Curtin, Sayan Das, Alex Davies, Laura De Lorenzo, Dripto M. Debroy, Sean Demura, Michel Devoret, Agustin Di Paolo, Paul Donohoe, Ilya Drozdov, Andrew Dunsworth, Clint Earle, Thomas Edlich, Alec Eickbusch, Aviv Moshe Elbag, Mahmoud Elzouka, Catherine Erickson, Lara Faoro, Edward Farhi, Vinicius S. Ferreira, Leslie Flores Burgos, Ebrahim Forati, Austin G. Fowler, Brooks Foxen, Suhas Ganjam, Gonzalo Garcia, Robert Gasca, Élie Genois, William Giang, Craig Gidney, Dar Gilboa, Raja Gosula, Alejandro Grajales Dau, Dietrich Graumann, Alex Greene, Jonathan A. Gross, Steve Habegger, John Hall, Michael C. Hamilton, Monica Hansen, Matthew P. Harrigan, Sean D. Harrington, Francisco J. H. Heras, Stephen Heslin, Paula Heu, Oscar Higgott, Gordon Hill, Jeremy Hilton, George Holland, Sabrina Hong, Hsin-Yuan Huang, Ashley Huff, William J. Huggins, Lev B. Ioffe, Sergei V. Isakov, Justin Iveland, Evan Jeffrey, Zhang Jiang, Cody Jones, Stephen Jordan, Chaitali Joshi, Pavol Juhas, Dvir Kafri, Hui Kang, Amir H. Karamlou, Kostyantyn Kechedzhi, Julian Kelly, Trupti Khaire, Tanuj Khattar, Mostafa Khezri, Seon Kim, Paul V. Klimov, Andrey R. Klots, Bryce Kobrin, Pushmeet Kohli, Alexander N. Korotkov, Fedor Kostritsa, Robin Kothari, Borislav Kozlovskii, John Mark Kreikebaum, Vladislav D. Kurilovich, Nathan Lacroix, David Landhuis, Tiano Lange-Dei, Brandon W. Langley, Pavel Laptev, Kim-Ming Lau, Loïck Le Guevel, Justin Ledford, Kenny Lee, Yuri D. Lensky, Shannon Leon, Brian J. Lester, Wing Yan Li, Yin Li, Alexander T. Lill, Wayne Liu, William P. Livingston, Aditya Locharla, Erik Lucero, Daniel Lundahl, Aaron Lunt, Sid Madhuk, Fionn D. Malone, Ashley Maloney, Salvatore Mandrá, Leigh S. Martin, Steven Martin, Orion Martin, Cameron Maxfield, Jarrod R. McClean, Matt McEwen, Seneca Meeks, Anthony Megrant, Xiao Mi, Kevin C. Miao, Amanda Mieszala, Reza Molavi, Sebastian Molina, Shirin Montazeri, Alexis Morvan, Ramis Movassagh, Wojciech Mruczkiewicz, Ofer Naaman, Matthew Neeley, Charles Neill, Ani Nersisyan, Hartmut Neven, Michael Newman, Jiun How Ng, Anthony Nguyen, Murray Nguyen, Chia-Hung Ni, Thomas E. O'Brien, William D. Oliver, Alex Opremcak, Kristoffer Ottosson, Andre Petukhov, Alex Pizzuto, John Platt, Rebecca Potter, Orion Pritchard, Leonid P. Pryadko, Chris Quintana, Ganesh Ramachandran, Matthew J. Reagor, David M. Rhodes, Gabrielle Roberts, Eliott Rosenberg, Emma Rosenfeld, Pedram Roushan, Nicholas C. Rubin, Negar Saei, Daniel Sank, Kannan Sankaragomathi, Kevin J. Satzinger, Henry F. Schurkus, Christopher Schuster, Andrew W. Senior, Michael J. Shearn, Aaron Shorter, Noah Shutty, Vladimir Shvarts, Shraddha Singh, Volodymyr Sivak, Jindra Skruzny, Spencer Small, Vadim Smelyanskiy, W. Clarke Smith, Rolando D. Somma, Sofia Springer, George Sterling, Doug Strain, Jordan Suchard, Aaron Szasz, Alex Sztein, Douglas Thor, Alfredo Torres, M. Mert Torunbalci, Abeer Vaishnav, Justin Vargas, Sergey Vdovichev, Guifre Vidal, Benjamin Villalonga, Catherine Vollgraff Heidweiller, Steven Waltman, Shannon X. Wang, Brayden Ware, Kate Weber, Theodore White, Kristi Wong, Bryan W. K. Woo, Cheng Xing, Z. Jamie Yao, Ping Yeh, Bicheng Ying, Juhwan Yoo, Noureldin Yosri, Grayson Young, Adam Zalcman, Yaxing Zhang, Ningfeng Zhu, Nicholas Zobrist · arXiv:2408.13687 · 2024
    arxiv.org/abs/2408.13687
  7. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits reuse permitted with attribution
    Craig Gidney and Martin Ekeraa · arXiv:1905.09749 · 2019
    arxiv.org/abs/1905.09749
  8. How to factor 2048 bit RSA integers with less than a million noisy qubits reuse permitted with attribution
    Craig Gidney · arXiv:2505.15917 · 2025
    arxiv.org/abs/2505.15917
  9. Shor's algorithm is possible with as few as 10,000 reconfigurable atomic qubits linked only, not reproduced
    Madelyn Cain, Qian Xu, Robbie King, Lewis R. B. Picard, Harry Levine, Manuel Endres, John Preskill, Hsin-Yuan Huang, Dolev Bluvstein · arXiv:2603.28627 · 2026
    arxiv.org/abs/2603.28627
  10. A verifiable quantum advantage linked only, not reproduced
    Xiao Mi and Kostyantyn Kechedzhi (Google Quantum AI) · 2025
    research.google/blog/a-verifiable-quantum-advantage/
  11. NIST Releases First 3 Finalized Post-Quantum Encryption Standards linked only, not reproduced
    National Institute of Standards and Technology · 2024
    www.nist.gov/news-events/news/2024/08/nist-releases-first-3-finalized-post-quantum-encryption-standards
  12. Transition to Post-Quantum Cryptography Standards, NIST IR 8547 initial public draft linked only, not reproduced
    Dustin Moody, Ray Perlner, Andrew Regenscheid, Angela Robinson & David Cooper (NIST) · 2024
    csrc.nist.gov/pubs/ir/8547/ipd