Tech companies are racing to make quantum computers available to customers. A new scheme from researchers in Singapore and Japan could help customers establish trust in what they get if they buy time on such machines - and protect companies from dishonest customers.
Quantum computers have the potential to solve problems that are beyond the reach of even today's biggest supercomputers, in areas such as drug modelling and optimisation.
"Our approach gives a way to generate a proof that a computation was correct, after it has been completed," explains Joseph Fitzsimons, a Principal Investigator at Singapore's Centre for Quantum Technologies and Assistant Professor at the Singapore University of Technology and Design.
Fitzsimons carried out the work with colleague Michal Hajdusek and collaborator Tomoyuki Morimae, who is at Kyoto University in Japan. Their proposals are published 22 January in Physical Review Letters.
Quantum computers today are bulky, specialised machines that require careful maintenance, meaning that people are more likely to access machines owned and operated by a third party than to have their own - like a quantum version of a cloud service.
Customers sending off data and programmes to a quantum computer will want to check that their instructions have been carried out as they intended. This problem of verification has been tackled before, but previous solutions required the customer to interact with the quantum computer while it was running the computation.
That kind of back-and-forth communication isn't necessary in the new scheme. "If you receive a result that look fishy, you can choose to verify the result, essentially retrospectively," says Fitzsimons. Verification guards against a quantum computer that does not perform correctly because of an accidental fault or even malicious tampering.
The improvement comes from how the calculation is checked. "The approach is completely different. We try to produce a state which can be used as a witness to the correctness of the computation. The previous approaches had some kind of trap built into the computation that gets checked as you go along," explains Fitzsimons.
The witness state registers each step of the computation. This means it must have as many bits as the computation has steps. For example, if a computation has 1000 steps, on 100 qubits, the witness would need to be 1100 qubits long.
The research team present two post-hoc verification schemes, based on different ways of testing the witness state. The first requires the customer to be able to send and measure quantum bits. In practice, this means they would need some specialized hardware and a line for sending these qubits to the owner of the quantum computer. The customer then measures the witness directly.
In the second scheme, the customer can be without any quantum tools - communication over the regular internet would do - but the quantum computer doing the calculation must be networked with five other quantum computers that help to check the witness state, playing a role as provers.
"It will be difficult to do an experiment to demonstrate post-hoc verification, but maybe not impossible", says Fitzsimons. A challenge is the size of the quantum computers available today - the biggest are around 50 qubits. Another is that the networked setups required for the prover schemes don't exist - at least not yet.
The researchers wrap up their paper by pointing out an interesting advantage of the post-hoc verification scheme: It's not only the customer who could check that a computation was carried out correctly. The scheme allows 'public verifiability'. The witness could be checked by a trusted third party, such as a court. This could protect the company if, say, a customer claimed the computation was not done correctly to avoid paying for the service.
"Post hoc verification of quantum computation" Physical Review Letters 120, 040501 (2018)
This paper combines results found in the following preprints:>
"Post hoc verification of quantum computation" Joseph F. Fitzsimons, Michal Hajdušek https://arxiv.org/abs/1512.04375 "Post hoc verification with a single prover" Tomoyuki Morimae, Joseph F. Fitzsimons https://arxiv.org/abs/1603.06046
Principal Investigator, Centre for Quantum Technologies at the National University of Singapore
Assistant Professor, Singapore University of Technology and Design
Research Fellow, Centre for Quantum Technologies at the National University of Singapore
Senior Lecturer, Yukawa Institute for Theoretical Physics, Kyoto University, Japan
Tomoyuki Morimae is supported by the JST ACT-I No.JPMJPR16UP, Grant-in-Aid for Scientific Research on Innovative Areas No.15H00850 of MEXT Japan, and the JSPS Grant-in-Aid for Young Scientists (B) No.26730003 and No.17K12637. Joseph Fitzsimons acknowledges support from Singapore's Ministry of Education and National Research Foundation, and the Air Force Office of Scientific Research under AOARD grant FA2386-15-1-4082. This material is based on research funded in part by the Singapore National Research Foundation under NRF Award NRF-NRFF2013-01. This research is supported by the National Research Foundation, Prime Minister's Office, Singapore under its Competitive Research Programme (CRP Award No.NRF-CRP14-2014-02).
Physical Review Letters