Outsourcing computations to a quantum computer you can not trust.
Quantum computers hold great promise, but to what extent can we trust the outcome of these elusive machines? In her PhD thesis, Yfke Dulek investigates ways to delegate computations to a quantum computer, focussing on the question how trustworthy the outcomes will be. Her research could pave the way for creating security guarantees in quantum computing.
When practical quantum computers become a reality in the future, they could be used as supercomputers or engines behind cloud services that can perform your calculations remotely. It’s the elusive laws of quantum physics that lie behind the power of quantum computers. Utilizing the enormous computational capabilities also brings along the uncertainty that surrounds the quantum world. How can you be sure that the output corresponds to the computation that was supposed to be carried out? How can you verify that nobody cheated during the protocol?
Verification is tricky in quantum computing, because of the unique nature of quantum data: you cannot copy a quantum state. This would have been handy to keep a ‘paper trail’ of the computation, allowing a way to reconstruct the computation. It’s even impossible to measure a quantum state without potentially disturbing the data.
Delegating and distributing
To overcome this situation, PhD researcher Yfke Dulek developed cryptographic protocols for delegating and distributing computations on quantum data. She considered various scenarios. In the first setting, a client outsources a quantum computation to a potentially untrustworthy server with minimal interaction during the computation. The second setting was a group of quantum computers on a network performing a joint computation. The last setting was a programmer publishing a piece of code that can be run without revealing the underlying algorithm. In this last setting, instead of constructing a protocol and proving it secure, Dulek showed that full security is impossible to achieve.
Quantum cryptographer’s toolbox
The developed protocols are relevant on both a theoretical and a practical level, says Dulek. On a theoretical level, it settles open questions about core cryptographic questions, such as the existence of (quantum) homomorphic encryption, which can now be added to the quantum cryptographer’s toolbox.
On a practical level, these protocols could be useful in a potential future scenario where quantum computers are available, but can only be logged into remotely, similarly to the supercomputing clusters we know today. In such a scenario, security guarantees such as privacy and verifiability are vital.
Valuable non-quantum cryptography
The development of these protocols has been possible using a technique that is already widely accepted in non-quantum cryptography. Its basic premise is that attackers are limited in the amount of computational resources they can spend on an attack. In the quantum setting, it was sometimes assumed that such ‘computational assumptions’, which sacrifice a small amount of security, are unnecessary. “My research confirms that they actually have a lot of value in the quantum setting as well, because it was known that some of these protocols are impossible without them”, says Dulek.
Practical protocols
According to Dulek, a lot of efficiency still has to be gained, in order to really make these protocols practical. “They are efficient on a theoretical level” says Dulek. “But the required resources are nowhere near what a quantum computer can offer today, or even in the near future. Additionally, since these protocols are designed to be used on a network, one would have to account for the noise that is naturally present on the communication channels, and ensure that it does not cause the verification procedures to fail.”
Future research
Dulek performed her PhD research at CWI's Algorithms & Complexity group and QuSoft, with her work being partially funded by the Institute for Logic, Language and Computation. She continues her work at CWI and QuSoft as a postdoctoral researcher, funded by a three-year Ada Lovelace Fellowship from the Quantum Software Consortium. “During that time, I hope to consider more questions of the possibility of impossibility of quantum cryptographic primitives, and explore their connections with complexity theory.”
Awarding quantum homomorphic encryption
During her PhD research period, Dulek also spent a spring semester as a Research Fellow at the Simons Institute for the Theory of Computing in Berkeley, California. This programme brought together researchers from around the world to participate in workshops, seminars, and research on quantum computing.
Dulek’s work on quantum homomorphic encryption was awarded in 2016, when she received a Young Talent Award from the Royal Holland Society of Sciences and Humanities. In 2017 her work was recognized with a Student Paper Award at the Quantum Information Processing conference. One year later she was an invited speaker at the workshop Quantum Innovators in Computer Science and Mathematics, hosted by University of Waterloo in Canada.
Dulek defended her thesis at the University of Amsterdam. Her research was supervised by QuSoft researcher Dr Christian Schaffner and Prof. Harry Buhrman, executive director of QuSoft and leader of the Algorithms & Complexity Group at CWI.