Computer scientists take on the quantum challenge
For a long time, the development of quantum computers was concerned with theoretical and hardware aspects. But as the focus shifts towards programming, software and security issues, the classical computer sciences are coming back into play.
Physicists had long nurtured the ambition to build a quantum computer. In the early 1980s, one of the most famous among them, Richard Feynman (1918?–1988), questioned whether it would ever be possible to efficiently compute and simulate quantum physics phenomena using a conventional computer. He argued that digital computers couldn’t compute fast enough to calculate and simulate the quantum effects that typically occur within atoms and molecules and between elementary particles – at least not within a reasonable period of time.
Initially, he proposed building a quantum computer based not on digital coding but rather on a direct imitation of quantum systems. His core idea, which continues to inspire the development of quantum computers to this day, was that certain properties of quantum mechanics could be harnessed for computation. Specifically, this would mean taking advantage of two quantum states of particles: superposition and entanglement.
The principle of superposition, for example, can be exploited by quantum computers to carry out faster calculations. While digital computers use binary bits that can only take on the states of one or zero, quantum computers use quantum bits, or qubits, to process information. Qubits can be one or zero, and they can also be both one and zero at once, a state we call superposition. This crucial difference enables a huge leap in computing speed for certain computational problems.
In future, quantum computers promise to perform ultra-efficient calculations that normal computers cannot solve in a reasonable period of time, a milestone sometimes referred to as quantum supremacy. Although scientists have yet to find conclusive proof of the existence of quantum supremacy, recent technical advances have been impressive. In 2019, Google claimed to have achieved quantum supremacy for a specific computational problem for the first time, having built a quantum computer that required only 200 seconds to solve a problem that would have taken a conventional computer 10,000 years.
Encryption could be cracked
Right now, quantum computers are too small and error-prone to pose any serious threat to today’s digital computers, which are capable of performing billions of computations per second. Even Google’s quantum computer was only able to prove its supremacy in a single, specific task. Nonetheless, quantum technologies have now reached a stage where their development lies in the hands of more than just physicists. Today, many computer scientists are “quantum curious”, according to ETH Computer Science Professor Kenneth Paterson. He conducts research in the field of cryptography and works on ways of securely processing, transferring and storing information. “We’ve been ’quantum aware’ in my area of research ever since quantum computing started to become a bigger issue in cryptography about ten years ago,” says Paterson. “As soon as someone builds a quantum computer that is sufficiently large-scale and reliable, the current encryption framework of the internet will cease to be secure, because quantum computing could be used to crack that encryption.”
The encryption and security protocols that run behind the scenes whenever we log on to social media, make an online purchase, use online banking or send an email are all based on integer factorisation and related problems that are vulnerable to Shor’s algorithm. Integer factorisation is the process of breaking down a large composite integer into its prime factors. This requires huge computing power, which is why there is still no algorithm – that is, no calculating procedure – that a digital computer can use to efficiently solve a factorisation problem. Back in 1994, however, mathematician Peter Shor created an algorithm specially designed for quantum computing, which can find the prime factors of composite integers significantly faster than classical algorithms. Shor’s ideas can be used to crack the other forms of public key cryptography in use today.
Today’s quantum computers are too small and error-prone to run Shor’s algorithm. In principle, however, it is clear that any quantum computer that is powerful and reliable enough to do so would be able to perform factorisation within a reasonable period of time. The moment this situation occurs, factoring-based cryptography and related techniques currently in widespread use will no longer be secure. Not all of cryptography will be affected, of course; for example, quantum computing won’t seriously affect the security of encryption methods that rely solely on secret-key cryptography. But public-key cryptography – which currently forms the basis for securing over 90 percent of web traffic – will definitely be at risk.
Translating ideas
According to Paterson, a quantum computer would need millions of quantum bits to crack a security key. Scientists at ETH Zurich are currently running quantum computers with up to 17 qubits. On the development side, researchers are on the brink of reaching a new phase of mid-sized quantum computing systems with 50 to 100 qubits, though these are still susceptible to errors. “But we might see a sudden breakthrough in the power of quantum computers, and it could take at least ten years to modify today’s public key cryptography. That’s why we’re getting ready now,” says Paterson. His group has co-developed a new quantum-safe algorithm that is being evaluated in an on-going worldwide competition to select new, quantum-secure algorithms.
People sometimes ask Benjamin Bichsel whether he feels his research will have been in vain should large-scale, reliable quantum computers eventually turn out to be unfeasible. “I think that’s the wrong question,” he says. “But I do wonder what we’ll do if quantum computers end up working brilliantly and we don’t have a clue how to programme them efficiently!” Bichsel works in the research group led by computer science professor Martin Vechev, whose group developed the first intuitive high-level programming language for quantum computing in 2020.
It will take special programming languages to properly exploit the potential of quantum computers. “Quantum programming languages are essential to translate ideas into instructions that can be executed by a quantum computer,” wrote Microsoft researchers in 2020 in the science journal Nature. The authors included Bettina Heim and Matthias Troyer, who had previously worked as researchers at the ETH Institute for Theoretical Physics.
Today’s quantum programming languages are tied closely to specific hardware. These “hardware description languages” focus on the behaviour of circuits and how to optimise them. In contrast, the Silq programming language developed by Martin Vechev’s group abstracts from the technical details.
Over a year has passed since Silq was launched; as the first high-level quantum programming language, it has already won acclaim for its elegance and internal coherence. Martin Vechev and his team have also earned praise for their innovative contribution towards reducing errors in quantum computing. In a further article about Silq, Nature explicitly refers to the “uncomputation” feature that enables Silq to automatically reset temporary values “rather than forcing programmers to do this tedious work manually”.
A computer processes a task in several intermediate steps, creating intermediate results or “temporary values” in the process. In classical computers, these values are erased automatically to free up memory. This task is a lot more complex in the case of quantum computers, however, since the principle of entanglement means that previously calculated values may interact with current ones and jeopardise the calculation process. That makes the ability to automatically clean up temporary values a key part of quantum computing.
A holistic view of computing
The question of whether Silq can hold its own against the quantum programming languages developed by technology giants Microsoft, IBM and Google – Q#, Qiskit and Cirq, respectively – is still very much up in the air. But, in the meantime, Vechev’s team have also succeeded in transferring automatic uncomputation to Qiskit. “It’s very encouraging to see that we can transfer key Silq concepts to other lan?guages – especially since automatic uncomputation improves the efficiency of quantum computing with Qiskit,” says Martin Vechev.
In the long run, there will be less of a focus on computer scientists writing languages and software for hardware developed by physicists. Instead, the emphasis will shift to developing programming languages hand in hand with quantum algorithms, quantum hardware, quantum software, quantum applications and workflows. “If we genuinely want to make quantum computing a reality, we will need to make this new approach part of a fully fledged computer system in which multiple components combine to solve specific problems efficiently,” says Paterson.
This text appeared in the 21/03 issue of the ETH magazine Globe.
About the persons
Kenneth Paterson is Professor of Computer Science at the Institute of Information Security, where he leads the Applied Cryptography Group.
Martin Vechev is a professor at the Institute for Programming Languages and Systems and heads the Secure, Reliable, and Intelligent Systems Lab (SRI) research group.