SUNNYVALE, CA–(BUSINESS WIRE)–NTT Research, Inc., a division of NTT (TYO:9432), today announced that a scientist from its Cryptography and Information Security (CIS) Laboratory and a colleague from NTT Social Informatics Laboratories (SIL) have written a groundbreaking paper on quantum an advantage. The paper was selected to be presented at the IEEE’s annual Foundations of Computer Science Symposium (FOCS), which runs Oct. 31-Nov. 3 in Denver. The paper, titled “Verifiable Structure-Free Quantum Advantage,” was co-authored by Dr. Takashi Yamakawa, a distinguished researcher at NTT SIL, and Dr. Marc Jandry, a senior scientist at the NTT Research CIS Lab. The work was performed in part at Princeton University, where Dr. Yamakawa was a visiting researcher and Dr. Gendry also served as an assistant professor of computer science.

The topic of the quantum advantage (or quantum speedup) is about the kinds of problems that quantum computers can solve faster than classical or non-quantum computers, and how much faster they are. The problems in question are usually described as non-deterministic of the polynomial time (NP) class. How much advantage can vary widely. A quantum computer may be able to solve a particular problem in a minute or a second, which takes a classical computer a week or possibly incredible exponential time. In this paper, the authors address the challenge of verifying this superiority and doing so effectively. To date, demonstrations of quantum advantage involve significant “structure” or back-and-forth communication between two or more parties. The breakthrough of the Yamakawa and Zhandry paper is to demonstrate an NP hard problem where verification is possible without structure.

“This is the first time we’ve seen exponential quantum speedup for an NP search problem that only requires a random oracle,” said University of Texas at Austin computer science professor Dr. Scott Aronson, who commented on an early version of the paper during at a workshop on June 13, 2022 at the Simons Institute for Theory of Computation. Requiring only an arbitrary oracle, ie. theoretical black box that generates random responses to each query, Yamakawa and Jandry built their problem on unstructured computational assumptions. As such, their problem is more closely related to one-way functions rather than structured ones such as those found in public-key cryptography. This one-way alignment facilitates efficient inspection.

“It is exciting to see NTT-affiliated cryptographers collaborate on research that again deserves the ‘breakthrough’ label, especially in a paper that enriches our understanding of quantum computing, another area of focus for us at NTT Research,” said Kazuhiro Gomi, president and CEO of NTT Research. “Congratulations and best wishes to all participants in this prestigious IEEE conference.”

The NP search problem that Yamakawa and Jandry created was a two-in-one problem that involves finding 1) a n-character string that is the codeword of a given error-correcting code, and 2) an n-character string where each symbol is mapped to zero under the random oracle. Each problem individually is easy. But finding a single character string that is both a code word and converts to zero is much more difficult, at least classically. “If you’re quantum, you can solve this in polynomial time,” Dr. Gendry said, “but if you’re classical, at least if you’re in that black-box model, you need exponential time.” On the other hand, having given a potential solution, it is easy to check by checking that it solves each of the two problems separately. Note that, as befits a FOCS paper, this work is basic or fundamental. As pointed out in Dr. Aaronson’s talk at the Simons Institute (discussed in this NTT Research blog article), the Yamakawa-Jandry argument falls into a class of speedups that can be easily verified mathematically but cannot be demonstrated in practice from an actual quantum computer anytime soon. Beyond its innovative verification scheme, however, the paper also points to something new about the extent of quantum speed-up.

“Prior to our work, we had examples of quantum advantage for NP problems like factorization or, in the black box setting, finding a period. But it turns out that the quantum algorithm underlying all these examples is fundamentally period-finding – although showing how to apply period-finding to these examples is often non-trivial,” Dr Jandry said. “Our paper shows that there is at least a second case. You could optimistically interpret this as saying that there is hope that the quantum advantage is more widespread than we may have previously thought.”

Sponsored by the Technical Committee on Mathematical Foundations of Computing (TCMF) of the IEEE Computer Society, FOCS is the premier conference in the field of theoretical computer science. The call for papers for FOCS 2022, the 63rd such annual gathering, listed quantum computing as one of 17 general areas of interest. The Yamakawa-Zhandry report is scheduled to be released on October 31, 2022, at 10:15 a.m. MT. To learn more and register for this event, please visit the FOCS 2022 website.

About NTT ResearchNTT Research opened its offices in July 2019 as a new Silicon Valley startup to conduct basic research and advanced technologies that promote positive change for humanity. Three laboratories are currently housed at NTT’s research facilities in Sunnyvale: the Physics and Informatics (PHI) Laboratory, the Cryptography and Information Security (CIS) Laboratory, and the Medical and Health Informatics (MEI) Laboratory. The organization aims to upgrade reality in three areas: 1) quantum information, neuroscience and photonics; 2) cryptographic and information security; and 3) medical and health informatics. NTT Research is part of NTT, a global provider of technology and business solutions with an annual research and development budget of $3.6 billion.

NTT and the NTT logo are registered trademarks or trademarks of NIPPON TELEGRAPH AND TELEPHONE CORPORATION and/or its affiliates. All other product names mentioned are trademarks of their respective owners. © 2022 NIPPON TELEGRAPH AND TELEPHONE CORPORATION