World's first new algorithm shows quantum computers can solve faster than classical computers
Showing a verifiable advantage in problems using functions without a "structure" such as periodicity

Tokyo - October 31, 2022 - NTT Corporation (President and CEO: Akira Shimada, "NTT") has devised a new quantum algorithm for the first time in the world, which shows the superiority of a verifiable quantum computer (quantum advantage) to a problem using a function whose output has no "structure" such as periodicity. This is the first proposal for a verifiable quantum advantage based on an essentially new idea in about 30 years since Shor's factorization algorithm (1994). This achievement is expected to promote the research of quantum algorithms for problems that have been considered difficult to find practical quantum algorithms, and to expand the scope of application of quantum computers in the future.
The result will be presented at the IEEE Symposium on Foundations of Computer Science (FOCS) 2022 (*1), the premier international conference in theoretical computer science.

1．Background

Quantum computers use the properties of quantum mechanics and are expected to be able to solve problems faster, such as quantum chemical calculations and certain kinds of simulations that are difficult to solve due to the explosive increase in computation time by existing classical computers, and there is a fierce competition in research and development around the world. From the point of research in computer science, it is a significant question of which problems have the quantum advantage, i.e., quantum computers can solve them faster than classical computers.
Shor's factorization algorithm, shown in 1994, is a well-known problem that quantum computers can solve faster than classical computers. However, there are many unanswered questions about which problems can be solved faster by quantum computers.

2．Results

Shor's factorization algorithm takes advantage of the fact that the remainder of a natural number's power has a "structure" like periodicity (Figure. 1). On the other hand, the output of the hash function (*2) has no "structure" such as periodicity (Figure. 2). No results have been known to show a verifiable quantum advantage for problems using functions without a "structure" like hash functions. In a paper (*3) co-authored with Dr. Mark Zandry of the NTT Research Cryptography & Information Security Lab, Takashi Yamakawa, a distinguished researcher at NTT, demonstrated for the first time in the world a quantum algorithm that shows a verifiable quantum advantage for a problem using only functions without a "structure." Yamakawa and co-author succeeded in defining a problem that can be solved by a quantum computer faster, but not by classical computers. The problem was finding an input such that the output of a random function without a structure, whose input is n bits and output is one bit, becomes zero. By adding a condition that the input is also an error correcting code (*4) to the problem, the problem can show a verifiable quantum advantage. The discovery of a quantum algorithm that shows a verifiable quantum advantage for this problem without a "structure" is expected to lead to the discovery of a fast quantum algorithm for a class of problems for which no fast algorithm by quantum computers has been previously known, and this is a breakthrough research result that could expand the application range of quantum computers in the future.

This work has attracted attention since it was published on arXiv (*5), and based on interviews with Yamakawa and others, an article was published on Quanta Magazine, a prominent website in the field of science (*6).
The results have also been adopted by the IEEE Symposium on Foundations of Computer Science (FOCS) 2022, the premier international conference in theoretical computer science, and will be presented at Session 1B, 10/31.

^(*1)FOCS 2022 https://focs2022.eecs.berkeley.edu/index.html

^(*2)Hash function: A function that obtains another short value from arbitrary data. They are used for things like electronic signatures. SHA -1 and its successor, SHA -2, are well-known.

^(*3)Verifiable Quantum Advantage without Structure. Takashi Yamakawa (NTT Social Informatics Laboratories), Mark Zhandry (Princeton University and NTT Research).

^(*4)Error correcting code: A code with a feature that allows the original correct code to be obtained even if an error occurs during data recording or transmission. The Reed-Solomon coding is well-known

^(*5)https://arxiv.org/abs/2204.02063

^(*6)Quantum Algorithms Conquer a New Kind of Problem https://www.quantamagazine.org/quantum-algorithms-conquer-a-new-kind-of-problem-20220711/

About NTT

NTT believes in resolving social issues through our business operations by applying technology for good. We help clients accelerate growth and innovate for current and new business models. Our services include digital business consulting, technology and managed services for cybersecurity, applications, workplace, cloud, data center and networks all supported by our deep industry expertise and innovation.
As a top 5 global technology and business solutions provider, our diverse teams operate in 88 countries and regions and deliver services to over 190 of them. We serve 85% of Fortune Global 100 companies and thousands of other clients and communities around the world.
For more information on NTT, visit www.global.ntt.