Writing a quantum algorithm? Avoid using a quantum computer

Zapata Computing, a 30-person startup in Boston, creates software for quantum computers. But when a customer has a problem it would like to solve, one of Zapata's first steps is to figure out how much it can avoid using a quantum machine.

That's because quantum computing is, like the tiny particles that underlie the technology, in a paradoxical state: It has arrived, but it isn't quite here. Quantum algorithms theoretically will be used for such transformative purposes as cracking encryption, simulating chemical reactions, and optimizing financial transactions. But the quantum machines that Google, IBM and other companies have so far put online for people to use aren't up to the task. Their limited number of quantum bits, or qubits, are unstable: They can't encode a lot of data yet.

So quantum software companies like Zapata are deploying their algorithms judiciously.

Say a customer wants to model the behavior of a molecule that could become a new drug, a problem thought to be a prime candidate for quantum computers. Zapata will "divide and conquer" the problem, says its chief technology officer, Yudong Cao. The startup determines which aspects of a molecule's behavior can be estimated well enough on a standard computer and which ones need the precise new insights of a quantum calculation. A quantum machine might be required only to simulate a tiny portion of a molecule where chemical reactions physically happen. "This little piece," Cao says, "would determine, let's say, the efficacy of the drug. This is the part where you want to model really accurately."

Determining which problems truly demand quantum computation is one of many challenges in this new software business. Quantum algorithms are very different from classical algorithms, and writing them requires people who are adept at the knotty mathematics of quantum physics. That's why quantum software companies are hiring many employees directly from academia.

"People have asked me, 'Oh, I'm a good programmer, couldn't I just take a boot-camp-like course and in three weeks learn how to program a quantum computer?' No, you probably couldn't," says Mark Jackson, the scientific lead for business development at Cambridge Quantum Computing, a quantum software startup based in the U.K. It has about 100 employees and says its customers include chemical, energy, financial and materials companies.

A classical computer is made up of electronic switches that are off or on to signify 0s or 1s. The programs that run those machines are full of "if-then" statements: If something is true, then do X; if something is false, then do Y.

But that stepwise logic doesn't work in a quantum computer. In a quantum computer, a qubit effectively signifies 0 and 1 at the same time. At any given moment, each of those values has some probability of existing. So a quantum algorithm has to harness that physical oddity. Unlike a classical one, it sets a starting state for the qubits (the input), and then there's a cascade of effects that leaves the qubits in a different state (which is the output).

Mathematically speaking — the language of computer algorithms — the range of probabilities for a qubit's value can be represented as a wave. And the interactions of all the qubits in a quantum computer can be mathematically described as multiple waves, which can amplify or cancel each other like physical waves in the ocean.

The job of a quantum algorithm is to mathematically describe the starting state of the qubits so that "the wave that encodes your solution gets much, much bigger, and the waves that don't contain your solution disappear," says Krysta Svore, general manager of quantum systems at Microsoft. "In a quantum algorithm, what we're actually doing is programming those waves."

People who use these quantum algorithms won't necessarily face such complexity: They will be able to make their queries from standard computers. Zapata, Cambridge Quantum, Microsoft, Google and other creators of quantum algorithms have created compilers: programs that do the nitty-gritty of encoding qubits and reading their outputs. Software developers who want applications to query a quantum computer in the cloud can write code in standard computing languages, such as Python and C++, and a compiler translates it into the steps necessary to make qubits do their thing. Microsoft has also developed a programming language, Q#, especially meant for facilitating quantum applications.

But while expertise in quantum mechanics won't be necessary to benefit from quantum algorithms, patience will be.

The most intriguing quantum algorithms — ones that would solve problems no classical computer could ever handle — will require machines with tens of thousands of reliable qubits. Today's machines have about 50 qubits and glitches that have to be accounted for with computationally costly error-correction techniques, and "we don't know yet whether such machines will be able to outperform classical computers for practically relevant problems," says Ashley Montanaro, a quantum-computation researcher at the University of Bristol and a co-founder of a quantum-software startup called PhaseCraft.

And as Scott Aaronson, a quantum-computing expert at the University of Texas, points out: "If something can also be done classically, then for the foreseeable future it will almost certainly be much cheaper and easier that way."

In the meantime, the main job of quantum-software providers might be to advise customers about how to prepare for the machines' eventual capabilities. "We are very careful to explain you won't have a commercial benefit for a while," Jackson says.

Cambridge Quantum Computing, which has raised $38 million from investors, won't need long to become profitable, according to CEO Ilyas Khan — but that's largely because the company is also earning revenue from selling encryption technology that uses principles of quantum mechanics. The market for quantum software will be slower to develop. "To use the internet analogy, we're at the dawn of 1995," Khan says.