"Everything we did was right on target"
In March 1996 Harry Buhrman was the first CWI scientist to publish a research paper in the then very young field of quantum computing. In the meantime, quantum computing has become a mature, international research field in which the business world also wants to get involved. The dream of solving practically relevant problems with a quantum computer is coming ever closer. In just under three decades quantum computing has grown from an exotic niche to a flourishing international research field with a leading position for CWI. Celebrating CWI’s 76th birthday today (11 February 2022), this longread tells the short history of quantum computing at CWI.
Research lines in quantum computing
Phase 0: How it started
In November 1994, Paul Vitanyi, then leader of the CWI research group Algorithms and Complexity, went to the IEEE Symposium on Foundations of Computer Science, held in Santa Fe, New Mexico (USA). There, the American researcher Peter Shor gave a lecture on a pioneering algorithm that he had developed.
With this algorithm, a quantum computer, a machine that could only be dreamt of at the time, would be able to quickly decompose large numbers into its prime factors. If successful, this machine would be able to crack globally used digital security systems. What other problems could a quantum computer solve much faster than a classical computer? Shor's audience wondered. The interest in the subject of quantum computing suddenly received a major boost.
"I heard Shor's lecture and found it very interesting," says Vitanyi, more than a quarter of a century later. "Before I flew back to the Netherlands, I went to Canada to visit my colleague Ming Li, with whom I had published our book An introduction to Kolmogorov complexity and its applications a year earlier. Inspired by Shor's algorithm, we wondered whether we could solve a similar problem: can a quantum computer efficiently determine whether two unlabelled graphs represented differently are of the same degree? Unfortunately, we came up with nothing, but the interest remained."
The first PhD students
After his visit to the conference and to his Canadian colleague, Vitanyi returned to CWI. The then director Gerard van Oortmerssen wanted the institute to do more practical research. "This change was called 'the tilt'," says Vitanyi. "To go along with this, I thought we could rename the Algorithms and Complexity group 'Quantum Computing and Advanced Systems Research'. I recruited Andre Berthiaume as a postdoc. He was the first person in the world to obtain a PhD in the new field of quantum computing. Berthiaume came from Gilles Brassard at the University of Montreal, a pioneer who invented quantum cryptography with Charles Bennett of IBM."
Paul Vitanyi
Not much later, Vitanyi first recruited Harry Buhrman as a postdoc, and then Barbara Terhal and Wim van Dam as PhD students. Vitanyi: "The hope was that at CWI we could relatively quickly pick the low-hanging fruit in an as yet unexplored field." Vitanyi himself wrote in 1995 in the review article 'Physics and the new computation' about new possibilities that were on the horizon of quantum computing.
Phase 1: "Everything we did was right on target".
PhD candidate Barbara Terhal came from theoretical physics, in particular quantum theory. In her PhD research at CWI, she studied the relationship between the quantum mechanical concept of entanglement and quantum algorithms. In 1999, Terhal became the first person in the Netherlands to obtain a PhD in quantum computing, and she did so cum laude. Later she became a professor at TU Delft.
Wim van Dam investigated in his PhD how a quantum computer can communicate with fewer bits than a classical computer. He obtained his PhD in physics from the University of Oxford in 2000 and in computer science from the University of Amsterdam in 2002, on research carried out at CWI together with Harry Buhrman. Nowadays Van Dam is the head of Quantum Algorithms at the company QC Ware in the US.
Buhrman started at CWI in 1994 and, like Vitanyi, came from the field of computational complexity, which investigates which arithmetical problems can and cannot be calculated efficiently on a computer. "I myself had first heard about quantum computing in a lecture by Gilles Brassard in 1992," says Buhrman. "When I came to work at CWI, I spoke extensively with Andre Berthiaume and decided to go further in the direction of quantum computing. The question of what you can and cannot calculate efficiently is extended by the quantum computer and I wanted to explore that further."
Harry Buhrman
The first publications
"Harry Buhrman went all in and did the most extraordinary things", says Vitanyi about Buhrman's contributions. Buhrman's first research result in quantum computing, and therefore also the first research result by a CWI researcher in this new field, dates from 1996. Title: A short note on Shor's factoring algorithm. And short it was: less than two pages.
First page of Harry Buhrman's publication on quantum computing in 1996
Two years later, in 1998, Buhrman published an article together with Richard Cleve and Avi Wigderson: Quantum vs. Classical Communication and Computation. That article has been widely cited over time. "It was a time of learning and trying," Buhrman says, "and just about everything we did in those years was hit."
Thus, within Vitanyi's research group, a subgroup specialised in quantum computing emerged in the second half of the 1990s and began to gain an international reputation. In 1997, theoretical computer scientist Ronald de Wolf started as a PhD student in the group. With Vitanyi and Buhrman as supervisors, De Wolf graduated cum laude in 2001 on the subject of 'Quantum Computing and Communication Complexity'.
In these early days, CWI researchers applied insights from quantum computing to communication acceleration, quantum versions of Kolmogorov complexity and quantum fingerprinting, among other things. They discovered ways to compute certain problems faster and some general limitations of quantum computers, discoveries that later became standard textbook material.
Phase 2: Broader European interest
Around 1999, research into quantum computing at CWI entered a new phase, Buhrman explains: "Until then, the work had been concentrated mainly in Montreal with Gilles Brassard, in Oxford with David Deutsch and Artur Ekert, in Bristol with Richard Jozsa, and with Charlie Bennett at IBM and Peter Shor at AT&T. But now more and more European colleagues were joining in. There was more international recognition for research into quantum software."
For example, between the year 2000 and 2004 Buhrman led the European research project Quantum Algorithms and Information Processing. Also, together with Ronald de Wolf, he organised and formed the 4th Workshop on Quantum Information Processing (QIP) that took place in Amsterdam in 2001. This conference attracted 150 participants from 24 countries, including pioneers such as Charles Bennett and David DiVincenzo (IBM Yorktown Heights), Gilles Brassard (Montreal) and the Dutch Nobel Prize winner in physics Gerard 't Hooft (Utrecht). This workshop has now become the most important in the field and has more than a thousand participants.
4th Workshop on Quantum Information Processing, Amsterdam (2001)
Defining quantum boundaries
In terms of research topics, the emphasis in this phase was on discovering the lower limits of quantum computing and on the theory of quantum information. Buhrman: "Which problems cannot be solved more efficiently with a quantum computer? We classified all kinds of problems and developed tools for designing quantum algorithms."
One of the important results of CWI researchers from these years is the 'quantum fingerprinting' algorithm that Buhrman, de Wolf and two colleagues from the University of Calgary published in 2001. This algorithm can compare large files from two separate sources exponentially more efficiently than is possible on a classical computer.
In 2016, Chinese researchers demonstrated a physical implementation of it for the first time. Using the algorithm, they compared two gigabytes of video data through the exchange of just 1,300 photons, about half of what would be needed classically.
Buhrman was appointed professor of Quantum Information Processing at the University of Amsterdam in 2000 and officially took over from Vitanyi in 2002, becoming head of the CWI research group Algorithms and Complexity. In addition to his CWI position, Ronald de Wolf was appointed professor of theoretical computer science at the University of Amsterdam (UvA) in 2011, a position he took over from Paul Vitanyi.
Phase 3: Establishment of QuSoft
Since 1994, research into quantum computing had grown considerably internationally. Nevertheless, the attention of the outside world was mainly focused on building a quantum computer, and thus on experimental physics and quantum hardware. In 1997, MIT researchers published the first measurement results for a single quantum bit. Thereafter, a quantum bit was added just about every year. In 2001, a rudimentary quantum computer with seven quantum bits was built that performed Shor's algorithm on the number 15 for the first time.
"Many hardware people said: the software will come naturally," Buhrman says. "But it doesn't. That is why we, as researchers of quantum software, started to claim a place on the stage. We had to keep saying: we're still here too!" That realisation began to spread more widely and eventually led to CWI and UvA jointly establishing the world's first quantum software research centre in 2015: QuSoft. In addition to his role as group leader of the CWI group Algorithms and Complexity and professor at UvA, Buhrman now became founder and co-director of QuSoft, together with UvA professor Kareljan Schoutens.
QuSoft-lustrum, december 2020
Quantum ecosystem in the Netherlands
Another new stimulus came in 2017 when the Ministry of Education, Culture and Science awarded a ten-year Gravitation Grant of 18.8 million euros to the Quantum Software Consortium, a collaboration between QuSoft, CWI, Leiden University, QuTech, TU Delft, UvA.
Within this consortium, quantum software researchers in the Netherlands are for the first time collaborating closely with quantum hardware researchers. The idea is that the Quantum Software Consortium will develop software for small quantum computers and for a small quantum Internet. This software must then be tested on the quantum hardware being developed at TU Delft and Leiden University and on a quantum network between Amsterdam, Delft, Leiden and The Hague.
Phase 4: Industry becomes interested
Quantum hardware made great strides in the first two decades of the 21st century. For example, in 2019, researchers at Google demonstrated a mini-quantum computer with 53 qubits that performed a calculation in just over three minutes that, according to the company, would take ten thousand years on a classical computer. A quantum computer that can solve practical problems is thus coming ever closer.
Partly because of this, research into quantum computing has entered a new phase, a phase in which the business community wants to be actively involved in the development of quantum software. Buhrman: "Companies do not want to lag behind their competitors and they want to know what they can gain from quantum computing in the future. QuSoft, for example, is now working with companies such as ABN AMRO, Bosch, Toyota and IBM."
What companies think they can gain from quantum computing lies roughly in three areas. Firstly, a better understanding of how nature works at the quantum mechanical level. In this field, the quantum computer can for example accelerate the development of new materials and catalysts. A second field is the optimisation of certain problems, such as finding the fastest route, optimising train traffic or searching through large databases. And a third area is that of information security. Quantum encryption, which not even a quantum computer can break, has already been developed.
Growth spurt
QuSoft has expanded the standing that CWI has had in the world of quantum computing since the late 1990s. By now, the quantum software research institute already has around seventy junior and senior researchers, some twenty of whom work at CWI. "We have grown so fast", Buhrman concludes, "that we have plans for our own building on the campus of the Amsterdam Science Park. Part of the UvA's experimental physics research will also be added there. A separate research institute for quantum computing would allow us to stand on our own feet, but the support of CWI remains important."
More information:
- CWI is also part of the Quantum.Amsterdam hub of the national ecosystem for excellence in quantum innovation Quantum Delta NL
- Quantum Application Lab
- Women in quantum development: WIQD
- Quantum Leap Africa
