Leaps in Quantum Computing

There are new computers that are generating some amazing results for solving problems in record time.  You won’t see these computers on the classic Top500 lists though, because they aren’t approaching computing in the same way. Using quantum computing algorithms like Shor’s algorithm for factoring large numbers, quantum computing holds the promise of solving problems that take exponential time on classical computers in linear time. Since many encryption algorithms rely on the factoring of large numbers this one application alone has drawn much attention. (For Dan Brown fans, think Digital Fortress on steroids.)

Figure 1 below shows Quantum Technology on Gartner’s Hype cycle diagram. It is still in the Innovation Trigger stage and more investment money is flowing into quantum computing technologies. (Given recent developments in funding for ML startups, perhaps ML has passed the peak of the Peak of Inflated Expectations at this point?)

Fig. 1: Hype cycle from Gartner [1]

This October (2023) has seen a couple of big announcements in quantum computing.  A research team from the University of Science and Technology of China in Anhui province published results in the Physical Review Letters on October 10, 2023, for a machine name JiuZhang 3 with 255 photons surpassing the 113 photons of its predecessor. The new machine reportedly solved a complex problem based on Gaussian boson sampling 1 million times faster than its predecessor and a billion years sooner than the fastest supercomputer. The question then arises, well what is the practical application of solving such problems? Recent research suggests that it could have potential applications in cryptography.[2] This has been a common issue though raised by skeptics, that the demonstration problems solved are often contrived and/or of little or no practical value. This has led some teams to focus more on practical applications and industry partnerships to focus on materials research like improving electric vehicle batteries and drug research. There’s also interest in financial services like portfolio optimization and fraud detection among others.

To get a feel for the class of problems where quantum computing may hold an edge over classical computing, Figure 2. Below shows the relationship with other known classifications. “The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP (“bounded error, quantum, polynomial time”). More formally, BQP is the class of problems that can be solved by a polynomial-time quantum Turing machine with error probability of at most 1/3.”[3] This points to the possibility of a class of problems that will have a clear advantage on quantum computers, but the counter argument is that perhaps in some cases the existence of efficient algorithms on a quantum computer indicates that there exist unknown algorithms that have better efficiency than existing known algorithms on classical computers. Of course, if anyone ever proved P=NP then it all collapses, but if you are more likely to bet that this won’t be proven then it leaves open the possibility that some class of problems will run more efficiently on quantum computers and maybe significantly so.

Fig. 2: BQP complexity relationship.

The second big announcement this month comes from Atom Computing. Atom Computing has created an atomic array consisting of 1,225 sites and populated with 1,180 qubits claiming the first quantum computer to exceed 1,000 qubits. One of the major advantages of having more qubits is it puts Arom Computing on a trajectory to incorporate fault-tolerance into their system. They are projecting to have systems available in 2024 and are on a path to fault-tolerant quantum computing in this decade. This is in line with projections by others in the industry for commercial realization in the next 5 to 10 years. Many skeptics believe that noise will perhaps be an unsurmountable barrier for quantum computing, so the ability to create real-time error correcting systems would be a major step forward for the industry.

Like GPUs and now AIUs, the expectations aren’t that quantum computing will supplant CPUs and classical computing, but that it will co-exist as yet another form of accelerated computing for a certain class of computing problems. For computer architecture this is an exciting time as the types of computing is branching in so many ways and will allow for creative combinations to drive ever more powerful and energy efficient ways of solving the most challenging problems today and into the future.

[1] Renaudin, Thomas, The Rising Quantum Computing Industry: Current State and Future Prospects
[2] Swayne, Matt, The Quantum Insider, China’s Photonic JiuZhang Series Sets (Yet Another) Speed Record
[3] Wikipedia, Quantum Complexity Theory: BQP
[4] Quantum startup Atom Computing first to exceed 1,000 qubits