Feature Articles: Designing a Future Where Everyone Can Flourish by Sharing Diverse Knowledge and Technologies
Vol. 21, No. 10, pp. 26–29, Oct. 2023. https://doi.org/10.53829/ntr202310fa4
Dilemma between Quantum Speedup and Computational Reliability—Overcoming Errors with Efficient Verification Methods for Quantum Computing
Quantum computers are expected to solve several problems faster than any classical computer. However, they may sometimes output incorrect answers because they are prone to errors. Therefore, to develop reliable quantum computers, it is essential to develop methods of verifying whether the outputs of quantum computers are correct. In this article, we introduce our recent research results on our verification methods.
Keywords: quantum computer, cloud quantum computing, quantum information processing
1. Advantages and issues with quantum computers
In 1994, Shor proposed a quantum algorithm that efficiently factors large integers . It is strongly believed that factorization is a hard problem for classical computers, and this hardness conjecture is used as evidence of the security of several modern cryptographic protocols. Shor’s algorithm is a well-known instance showing the computational advantage of quantum computers, and since his proposal, quantum computers have been extensively studied. The quantum computational advantage is known for several problems, such as the simulation of physical and chemical systems and the approximation of Jones polynomials. Despite these advantages, quantum computers face implementation challenges due to environmental noise. There are various methods for designing qubits; a qubit is the basic unit of information in quantum computers. When superconducting circuits are used as qubits, for example, errors can occur due to temporal fluctuations in the resonant frequency. In factorization, such errors are not significant. This is because the correctness of the output (i.e., the answer to a factorization) can be easily checked by executing multiplication on a classical computer; hence, it is easy to determine whether errors have occurred during the quantum computation. As mentioned above, quantum computers can also be applied to various problems other than factorization. For instance, when using a quantum computer to approximate Jones polynomials, there is no known classical method for efficiently checking whether the output is an accurate approximation. In other words, there is a dilemma caused by quantum superposition. This enables high-speed calculations of quantum computers but makes it difficult to verify the correctness of the outputs. To leverage the high computational power of quantum computers, it is necessary to address the impact of errors and develop techniques for resolving this dilemma.
2. Techniques to protect quantum computers from errors
This section discusses two techniques to suppress the impact of errors during quantum computations: quantum error correction and mitigation and verification of quantum computation. Quantum error correction is a technique that detects and corrects errors. The information of a single qubit is encoded using multiple physical qubits. Since it is currently challenging to prepare a large number of physical qubits, the implementation of quantum error correction is still limited to small-scale experiments. To overcome this limitation, quantum error mitigation has been proposed, which suppresses the impact of errors by repeating small-scale quantum computations instead of increasing the number of qubits. However, quantum error mitigation is applicable only to limited tasks, such as calculating expectation values, and generally requires an exponential number of executions of quantum computations. To apply quantum error correction or mitigation, some knowledge about the errors is required. Several quantum-error-correction protocols and quantum-error-mitigation methods cannot be used unless the error probability is sufficiently small.
Verification of quantum computation can be used even when the error probability is large. However, it cannot correct or mitigate errors; it can only detect errors. By solving the same problem multiple times with a quantum computer and verifying each answer, it is possible to extract the correct answers, i.e., the output that is not affected by errors. Therefore, verification can be considered effective for addressing the impact of errors.
As a summary, quantum error correction can correct errors but is applicable to limited situations with small error probabilities. Verification of quantum computation, however, can be used even when error probabilities are large but can only detect errors. Quantum error correction thus compensates for the verification drawbacks and vice versa. Therefore, both techniques are crucial for developing highly reliable large-scale quantum computers (see Table 1). In the following sections, we introduce some of our research results on our methods for verifying quantum computation.
3. Several verification methods
3.1 Verification of measurement-based quantum computation
There are several models of quantum computing. One is measurement-based quantum computation (MBQC). In the conventional approach known as the quantum circuit model, quantum computation is executed by first initializing qubits then applying quantum gates to them, followed by measurements. In MBQC, once a specific entangled state* called a graph state is prepared, any quantum computation can be carried out by sequentially measuring individual qubits. Since the graph state is independent of the problems to be solved, it can be prepared in advance before starting to solve the problems. When we design qubits by using light (more precisely, photons), single-qubit gates and measurements are relatively easy to conduct. However, the implementation of two-qubit operations is challenging and can only be done probabilistically (in linear optical quantum computing). In MBQC, two-qubit gates are only required during the preparation of the graph state. After starting to solve the problems, only simple operations, i.e., measurements, are needed. This is a significant advantage over the quantum circuit model. Therefore, MBQC has been applied to various quantum-information-processing tasks such as quantum cryptography and quantum communication.
When a quantum computer is developed in accordance with MBQC, the step of preparing a graph state is the most error-prone. Therefore, several methods have been proposed for verifying whether the graph state is correctly prepared. In 2019, we devised an efficient verification method, which was superior in efficiency to other verification methods at that time . To achieve this improvement, we were the first to apply a mathematical technique, which was previously used in quantum key distribution, to verification. Subsequently, we applied our verification method to quantum sensing  and experimentally demonstrated it in a small-scale optical experiment . These developments indicate a significant impact and expansion of our research in this field.
3.2 Verification of quantum-random-number generation
We extended the graph-state verification mentioned in the previous section to more complex quantum states called weighted graph states. This extension enables the verification of a family of quantum circuits called instantaneous quantum polynomial-time (IQP) circuits. This family of circuits can only execute a limited set of computations obtained regardless of the order of quantum gates to be applied (see Fig. 1), although this property may make the physical implementation of IQP circuits easier. Consequently, the computational power of IQP circuits should be weaker than that of an ideal full-fledged quantum computer since the computation on the latter heavily depends on the order of quantum gates. By using ideal IQP circuits, however, it is possible to generate random numbers that is difficult on classical computers. It is not easy to determine whether the generated numbers follow an ideal probability distribution or noisy one that is easily reproducible with classical computers. In 2019, we made it possible to efficiently check whether the random numbers are correctly generated by conducting verification of IQP circuits .
3.3 Verification of noisy intermediate-scale quantum computers
Quantum computers with computational capabilities weaker than full-fledged quantum computers, such as IQP circuits, are referred to as non-universal quantum computers. Some non-universal quantum computers are currently in use or expected to be developed in the near future. They are called noisy intermediate-scale quantum (NISQ) computers, which are small or medium-scale quantum computers with inevitable noise. As reviewed in another article in this journal , we proposed a verification method tailored for NISQ computers .
3.4 Verification of quantumness of quantum computers
Our methods introduced above require small-scale quantum measurement devices to execute verification. In other words, these methods verify the outputs of various quantum computers, such as MBQC, IQP circuits, and NISQ computers, by using another smaller quantum computer. To make verification of quantum computation more practical, it would be desirable to enable efficient verification using a classical computer. In 2018, Mahadev proposed a classical verification method  by using post-quantum cryptography, which is modern cryptography secure even against quantum attacks. Her method was a significant breakthrough in the field and was subsequently extended by many researchers. In 2022, by applying her technique, we also proposed a verification method for verifying the correct preparations and measurements of a special quantum state, so-called magic state . Quantum computation without magic states (specifically, computations limited to Clifford unitary operations) can be efficiently simulated with classical computers. Therefore, verifying magic states can be used to determine the presence of essential quantum properties in quantum computers.
We proposed various verification methods that make several types of quantum computers verifiable. Further improvements in many directions are necessary for their practical use. A possible direction would be to improve our methods and apply verification of quantum computation to cloud-quantum-computing systems. Companies, such as IBM and Amazon, provide cloud-quantum-computing systems, but they lack the verification features for users to check the correctness of their received results. By incorporating verification methods into existing systems, users can verify the accuracy of their received answers for themselves, and the companies providing the systems can transparently demonstrate the high performance of their quantum computers. Our goal is to achieve a society where anyone can benefit from quantum computers from anywhere. Toward this goal, we will continually contribute to the development of fundamental technologies in quantum computing.