Sunnyvale, Calif. – October 26, 2022 – NTT Research announced that a scientist from its Cryptography and Information Security (CIS) Lab and a colleague from the NTT Social Informatics Laboratories (SIL) have written a pathbreaking paper on quantum advantage. The paper was selected to be presented at the annual IEEE Symposium on Foundations of Computer Science (FOCS), which is taking place Oct. 31–Nov. 3 in Denver.
The co-authors of the paper, titled “Verifiable Quantum Advantage without Structure,” are Dr. Takashi Yamakawa, distinguished researcher at NTT SIL and Dr. Mark Zhandry, senior scientist in the NTT Research CIS Lab. The work was done in part at Princeton University, where Dr. Yamakawa was a visiting research scholar and Dr. Zhandry also serves as an assistant professor of computer science.
The topic of quantum advantage (or quantum speedup) relates to 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 commonly described as non-deterministic polynomial-time (NP) class. How much advantage could vary to a vast degree. A quantum computer may be able to solve a particular problem in a minute or a second that takes a classical computer a week, or possibly an unfathomably exponential amount of time. In this paper, the authors address the challenge of verifying this superiority, and doing so efficiently. To date, demonstrations of quantum advantage have involved significant “structure,” or back-and-forth communication among 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 that we’ve seen an exponential quantum speedup for an NP search problem, which only requires a random oracle,” said University of Texas at Austin Professor of Computer Science Dr. Scott Aaronson, who commented on an early version of the paper during a workshop on June 13, 2022, at the Simons Institute for the Theory of Computing. By only requiring a random oracle, i.e., a theoretical black box that generates random responses to each query, Yamakawa and Zhandry built their problem on unstructured computational assumptions. As such, their problem aligns more closely with one-way functions instead of structured ones, such as those found in public key cryptography. That one-way alignment facilitates efficient verification.
“It is exciting to see NTT-affiliated cryptographers collaborating on research that once again merits the label of ‘breakthrough,’ especially in a paper that enriches our understanding of quantum computing, another area of focus for us at NTT Research,” said Kazuhiro Gomi, NTT Research President and CEO. “Congratulations and best wishes to all participants in this prestigious IEEE conference.”
The NP search problem that Yamakawa and Zhandry devised was a two-in-one problem that entails finding 1) an n-symbol string that is a code word of a given error-correction code, and 2) an n-symbol string where each symbol is mapped to zero under the random oracle. Each problem separately is easy. But to find a single string of symbols that is both a codeword and maps to zero is much harder, at least classically. “If you’re quantum, you can solve this in polynomial time,” said Dr. Zhandry, “but if you’re classical, at least if you’re in this black-box model, you need exponential time.” On the other hand, given a potential solution, it is simple to verify it by checking that it separately solves each of the two problems. Note that, as befits a paper for FOCS, this work is basic or foundational. As pointed out in Dr. Aaronson’s talk at the Simons Institute (discussed in this NTT Research blog article), the Yamakawa-Zhandry argument falls into a class of speedups can be readily checked mathematically, but not demonstrated practically by an actual quantum computer any time soon. Beyond its pathbreaking verification scheme, however, the paper also points to something new concerning the extent of quantum speedup.
“Prior to our work, we did have examples of quantum advantage for NP problems, like factoring or, in the black box setting, period finding. But it turns out that the quantum algorithm underlying all these examples was basically period finding – though showing how to apply period-finding to these examples was often non-trivial,” said Dr. Zhandry. “Our paper shows there’s at least a second case. You could optimistically interpret that as saying there’s hope that quantum advantage is more widespread than maybe we previously thought.”
Sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), FOCS is a leading 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 paper is scheduled to be presented on Oct 31, 2022, at 10:15 am MT. To learn more about and register for this event, visit the FOCS 2022 website.
