NTT Research, Inc., a division of NTT, 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.
Recommended AI: Eric Tippetts Announces Version 3.0 of Innovative Network Marketing App
“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. “C************** and best wishes to all participants in this prestigious IEEE conference.”
Recommended AI: Consider Your DOOH Buying Methods Wisely: Direct Sales vs. Programmatic Buying
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, 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.”
Recommended AI: Understanding the Role of AI in Gaming
[To share your insights with us, please write to sghosh@martechseries.com]
Comments are closed.