What is quantum computing? Solutions to impossible problems

There’s no lack of hype in the computer industry, although even I have to admit that sometimes the technology does catch up to the promises. Machine learning is a good example. Machine learning has been hyped since the 1950s, and has finally become generally useful in the last decade.

Quantum computing was proposed in the 1980s, but still isn’t practical, although that hasn’t dampened the hype. There are experimental quantum computers at a small number of research labs, and a few commercial quantum computers and quantum simulators produced by IBM and others, but even the commercial quantum computers still have low numbers of qubits (which I’ll explain in the next section), high decay rates, and significant amounts of noise.

Quantum computing explained

The clearest explanation of quantum computing that I’ve found is in this video by Dr. Talia Gershon of IBM. In the video, Gershon explains quantum computing to a child, a teenager, a college student, and a graduate student, and then discusses quantum computing myths and challenges with Professor Steve Girvin from Yale University.

To the child, she makes the analogy between bits and pennies. Classical bits are binary, like pennies lying on the table, showing either heads or tails. Quantum bits (qubits) are like pennies spinning on the table, which could eventually collapse into states that are either heads or tails.

To the teenager, she uses the same analogy, but adds the word superposition to describe the states of a spinning penny. Superposition of states is a quantum property, commonly seen in elementary particles and in the electron clouds of atoms. In popular science, the usual analogy is the thought experiment of Schrödinger’s Cat, which exists in its box in a superposed quantum state of both alive and dead, until the box is open and it is observed to be one or the other.

Gershon goes on to discuss quantum entanglement with the teenager. This means that the states of two or more entangled quantum objects are linked, even if they are separated.

By the way, Einstein hated this idea, which he dismissed as “spooky action at a distance,” but the phenomenon is real and observable experimentally, and has recently even been photographed. Even better, light entangled with quantum information has been sent over a 50-kilometer optical fiber.

Finally, Gershon shows the teenager IBM’s quantum computer prototype with its dilution refrigerator, and discusses possible applications of quantum computers, such as modeling chemical bonds.

With the college student, Gershon goes into more detail about the quantum computer, the quantum chip, and the dilution refrigerator that takes the temperature of the chip down to 10 mK (milliKelvin). Gershon also explains quantum entanglement in more detail, along with quantum superposition and interference. Constructive quantum interference is used in quantum computers to amplify signals leading to the right answer, and destructive quantum interference is used to cancel signals leading to the wrong answer. IBM makes qubits out of superconducting materials.

With the grad student, Gershon discusses the possibility of using quantum computers to speed up key parts of the training of deep learning models. She also explains how IBM uses calibrated microwave pulses to manipulate and measure the quantum state (the qubits) of the computing chip.

The principal algorithms for quantum computing (discussed below), which were developed before even one qubit had been demonstrated, assumed the availability of millions of perfect, fault-tolerant, error-corrected qubits. We currently have computers with 50 qubits, and they are not perfect. New algorithms under development are intended to work with the limited numbers of noisy qubits we have now.

Steve Girvin, a theoretical physicist from Yale, tells Gershon about his work on fault-tolerant quantum computers, which don’t yet exist. The two of them discuss the frustration of quantum decoherence — “You can only keep your information quantum for so long” — and the essential sensitivity of quantum computers to noise from the simple act of being observed. They took a stab at the myths that in five years quantum computers will solve climate change, cancer, and . Girvin: “We are currently at the vacuum tube or transistor stage of quantum computing, and we are struggling to invent quantum integrated circuits.”

Quantum algorithms

As Gershon mentioned in her video, the older quantum algorithms assume millions of perfect, fault-tolerant, error-corrected qubits, which are not yet available. Nevertheless, it’s worth discussing two of them to understand their promise and what countermeasures can be used to protect against their use in cryptographic attacks.

Grover’s algorithm

Grover’s algorithm, devised by Lov Grover in 1996, finds the inverse of a function in O(√N) steps; it can also be used to search an unordered list. It provides a quadratic speedup over classical methods, which need O(N) steps.

Other applications of Grover’s algorithm include estimating the mean and median of a set of numbers, solving the collision problem, and reverse-engineering cryptographic hash functions. Because of the cryptographic application, researchers sometimes suggest that symmetric key lengths be doubled to protect against future quantum attacks.

Shor’s algorithm

Shor’s algorithm, devised by Peter Shor in 1994, finds the prime factors of an integer. It runs in polynomial time in log(N), making it exponentially faster than the classical general number field sieve. This exponential speedup promises to break public-key cryptography schemes, such as RSA, if there were quantum computers with “enough” qubits (the exact number would depend on the size of the integer being factored) in the absence of quantum noise and other quantum-decoherence phenomena.

If quantum computers ever become large and reliable enough to run Shor’s algorithm successfully against the sort of large integers used in RSA encryption, then we would need new “post-quantum” cryptosystems that don’t depend on the difficulty of prime factorization.

Quantum computing simulation at Atos

Atos makes a quantum simulator, the Quantum Learning Machine, which acts as though it has 30 to 40 qubits. The hardware/software package includes a quantum assembly programming language and a Python-based high-level hybrid language. The device is in use at a few national labs and technical universities.

Quantum annealing at D-Wave

D-Wave makes quantum annealing systems such as the DW-2000Q, which are a little different and less useful than general-purpose quantum computers. The annealing process does optimization in a way that is similar to the stochastic gradient descent (SGD) algorithm popular for training deep learning neural networks, except that it allows for many simultaneous starting points and quantum tunneling through local hills. D-Wave computers cannot run quantum programs such as Shor’s algorithm.

D-Wave claims that the DW-2000Q system has up to 2,048 qubits and 6,016 couplers. To reach this scale, it uses 128,000 Josephson junctions on a superconducting quantum processing chip, cooled to less than 15 mK by a helium dilution refrigerator. The D-Wave package includes a suite of open-source Python tools hosted on GitHub. The DW-2000Q is in use at a few national labs, defense contractors, and global enterprises.

Quantum computing at Google AI

Google AI is doing research on superconducting qubits with chip-based scalable architecture targeting two-qubit gate error

In 2018 Google announced the creation of a 72-qubit superconducting chip called Bristlecone. Each qubit can connect with four nearest neighbors in the 2D array. According to Hartmut Neven, the director of Google’s Quantum Artificial Intelligence lab, quantum-computing power is increasing on a double-exponential curve, based on the number of conventional CPUs that the lab needs to replicate results from their quantum computers.

In late-2019, Google announced that it had achieved quantum supremacy, the condition where quantum computers can solve problems that are intractable on classical computers, using a new 54-qubit processor named Sycamore. The Google AI Quantum team published the results of this quantum supremacy experiment in the Nature article, “Quantum Supremacy Using a Programmable Superconducting Processor.” 

Quantum computing at IBM

In the video that I discussed earlier, Dr. Gershon mentions that “There are three quantum computers sitting in this lab that anyone can use.” She is referring to IBM Q systems, which are built around transmon qubits, essentially niobium Josephson junctions configured to behave like artificial atoms, controlled by microwave pulses that fire microwave resonators on the quantum chip, which in turn address and couple to the qubits on the processor.

IBM offers three ways to access its quantum computers and quantum simulators. For “anyone” there is the Qiskit SDK, and a hosted cloud version called the IBM Q Experience (see screenshot below), which also provides a graphical interface for designing and testing circuits. At the next level, as part of IBM Q Network, organizations (universities and large companies) are provided with access to IBM Q’s most advanced quantum computing systems and development tools.

Qiskit supports Python 3.5 or later and runs on Ubuntu, macOS, and Windows. To submit a Qiskit program to one of IBM’s quantum computers or quantum simulators, you need IBM Q Experience credentials. Qiskit includes an algorithm and application library, Aqua, which provides algorithms such as Grover’s Search and applications for chemistry, AI, optimization, and finance.

IBM unveiled a new generation of IBM Q system with 53 qubits in late-2019, as part of an expanded fleet of quantum computers in the new IBM Quantum Computation Center in New York State. These computers are available in the cloud to IBM’s over 150,000 registered users and nearly 80 commercial clients, academic institutions and research laboratories.

IDG

Quantum computing at Intel

Research at Intel Labs has led directly to the development of Tangle Lake, a superconducting quantum processor that incorporates 49 qubits in a package that is manufactured at Intel’s 300-millimeter fabrication facility in Hillsboro, Oregon. This device represents the third-generation of quantum processors produced by Intel, scaling upward from 17 qubits in its predecessor. Intel has sent Tangle Lake processors to QuTech in the Netherlands for testing and work on system-level design.

Intel is also doing research on spin qubits, which function on the basis of the spin of a single electron in silicon, controlled by microwave pulses. Compared to superconducting qubits, spin qubits far more closely resemble existing semiconductor components operating in silicon, potentially taking advantage of existing fabrication techniques. Spin qubits are expected to remain coherent far longer than superconducting qubits, and to take much less space.

Quantum computing at Microsoft

Microsoft has been researching quantum computers for over 20 years. In the public announcement of Microsoft’s quantum computing effort in October 2017, Dr. Krysta Svore discussed several breakthroughs, including the use of topological qubits, the Q# programming language, and the Quantum Development Kit (QDK). Eventually, Microsoft quantum computers will be available as co-processors in the Azure cloud.

The topological qubits take the form of superconducting nanowires. In this scheme, parts of the electron can be separated, creating an increased level of protection for the information stored in the physical qubit. This is a form of topological protection known as a Majorana quasi-particle. The Majorana quasi-particle, a weird fermion that acts as its own anti-particle, was predicted in 1937 and was detected for the first time in the Microsoft Quantum lab in the Netherlands in 2012. The topological qubit provides a better foundation than Josephson junctions since it has lower error rates, reducing the ratio of physical qubits to logical, error-corrected qubits. With this reduced ratio, more logical qubits are able to fit inside the dilution refrigerator, creating the ability to scale.

Microsoft has variously estimated that one topological Majorana qubit is worth between 10 and 1,000 Josephson junction qubits in terms of error-corrected logical qubits. As an aside, Ettore Majorana, the Italian theoretical physicist who predicted the quasi-particle based on a wave equation, disappeared in unknown circumstances during a boat trip from Palermo to Naples on March 25, 1938.

The “Hello, World” program for Q# demonstrates “teleporting” the state of a qubit to another, entangled qubit. This particular exercise works with Visual Studio or Visual Studio Code. While Microsoft does not yet offer access to actual quantum computers in Azure, it does offer quantum simulators that run locally or in Azure.

Quantum hurdles

As we’ve seen, there is currently no single standard for quantum computers, qubit construction, or quantum programming. Several vendors have created quantum computers of their own design, and several vendors have created quantum-programming SDKs.

While quantum computing has great promise to solve problems that are too hard for classical computers to solve in reasonable amounts of time, they are not yet practical. The major problems to overcome are quantum decoherence and noise, qubit fragility, and scalability of quantum computers.

At this point only IBM offers cloud access to real quantum computers, but other vendors, including Intel and Microsoft, are working on quantum computers that may have less noise, longer coherence times, and higher density than ones based on superconducting Josephson junction qubits.