NTT scientists verify quantum advantage on unstructured computational assumptions for the first time

On October 27, NTT Research announced [1] that Dr. Mark Zhandry, a senior scientist in its Cryptography and Information Security (CIS) Laboratory, and Dr. Takashi Yamakawa, a distinguished researcher in NTT's Social Informatics Laboratory (SIL), have co-authored a groundbreaking paper on quantum dominance - "Structureless Verifiable Quantum Dominance" [2].

Left: Mark Zhandry; Right: Takashi Yamakawa

This paper was selected for presentation at the annual IEEE Foundations of Computer Science (FOCS) Symposium in Denver, Oct. 31-Nov. 3.

01First implementation: verifying quantum advantage on unstructured computational assumptions

Quantum advantage refers to what kinds of problems quantum computers can solve faster than classical/non-quantum computers, and how fast they can be. The problems in question are usually described as non-deterministic polynomial time (NP) classes. A quantum computer may solve a particular problem in a minute or a second, while a classical computer takes a week, or possibly an unacceptable exponential length of time.

In this paper, the authors discuss the challenges of verifying this superiority, and do so effectively. The breakthrough of Yamakawa and Zhandry's paper is the proof of an NP-hard problem, where no structure can be verified.

02Proving Mathematical Speedup of Quantum Computing in Two-in-One, NP Search Problems

Dr. Scott Aaronson, professor of computer science at the University of Texas at Austin, said, "This is the first time we've seen an exponential quantum speedup of an NP search problem that requires only one random instruction (oracle)." Aaronson commented on an earlier version of the paper at a June 13, 2022, workshop at the Simons Institute for Theory of Computing that by requiring only one random instruction, a theoretical black box that produces a random response to each query, the scientists built their problem on unstructured computational assumptions. As a result, their problem is closer to a one-way function than to a structured function, such as those found in public key ciphers; this one-way arrangement facilitates efficient verification.

The NP search problem designed by Yamakawa and Zhandry is a two-in-one problem that requires finding 1) a string of n symbols that is a codeword for a given error-correcting code; and 2) a string of n symbols, where each symbol is mapped to zero under random instructions.

Each problem is easy separately. But it's much harder to find a single string of symbols that is both a code word and mapped to zero, at least on a classical computer. "But with quanta, it is possible to solve this problem in polynomial time." Dr. Zhandry said, "But with a classical computer, it would take at least exponential time in this black-box model." On the other hand, given a potential solution, it would be simple to verify it by checking that it solves each of the two problems separately.

This work, however, is a fundamental study. As Dr. Aaronson pointed out in his talk, the Yamakawa-Zhandry argument belongs to a class of accelerations that can be easily checked mathematically, but will not be actually proven by an actual quantum computer in the near future. Not only that, but in addition to its groundbreaking verification scheme, the paper points out something new about the degree of quantum acceleration.

03Groundbreaking theoretical proof: A broader quantum advantage

Kazuhiro Gomi, President and CEO of NTT Research, said, "It is particularly rewarding to see research conducted in collaboration with cryptographers associated with NTT once again receive the 'breakthrough' label in a paper that enriches our understanding of quantum computing, which is one of our another area of focus for NTT Research."

"Prior to our work, we did have examples of quantum advantages on NP problems, such as factorization or cycle finding in a black box setup. But it turns out that the quantum algorithms behind all of these examples are essentially cycle finding; although showing how to apply cycle finding to these examples is often not difficult." Dr. Zhandry said, "Our paper shows at least a second scenario: the reader can be optimistic and interpret it as saying that there is hope and that the quantum advantage is perhaps more widespread than we previously thought."

Reference links:

[1]https://www.businesswire.com/news/home/20221026005295/en/NTT-Scientists-Demonstrate-New-Way-to-Verify-Quantum-Advantage

[2]https://arxiv.org/pdf/2204.02063.pdf