NTT Scientists Demonstrate New Way to Verify Quantum Advantage

October 26, 2022

SUNNYVALE, Calif., Oct. 26, 2022 — NTT Research today 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, please visit the FOCS 2022 website.

About NTT Research

NTT Research opened its offices in July 2019 as a new Silicon Valley startup to conduct basic research and advance technologies that promote positive change for humankind. Currently, three labs are housed at NTT Research facilities in Sunnyvale: the Physics and Informatics (PHI) Lab, the Cryptography and Information Security (CIS) Lab, and the Medical and Health Informatics (MEI) Lab. 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 technology and business solutions provider with an annual R&D budget of $3.6 billion.


Source: NTT Research

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industry updates delivered to you every week!

HPC Pioneer Gordon Bell Passed Away

May 22, 2024

Legendary computer scientist Gordon Bell passed away last Friday at his home in Coronado, CA. He was 89. The New York Times has a nice tribute piece. A long-time pioneer with Digital Equipment Corp, he pushed hard for de Read more…

ISC 2024 — A Few Quantum Gems and Slides from a Packed QC Agenda

May 22, 2024

If you were looking for quantum computing content, ISC 2024 was a good place to be last week — there were around 20 quantum computing related sessions. QC even earned a slide in Kathy Yelick’s opening keynote — Bey Read more…

Atos Outlines Plans to Get Acquired, and a Path Forward

May 21, 2024

Atos – via its subsidiary Eviden – is the second major supercomputer maker outside of HPE, while others have largely dropped out. The lack of integrators and Atos' financial turmoil have the HPC market worried. If Read more…

Core42 Is Building Its 172 Million-core AI Supercomputer in Texas

May 20, 2024

UAE-based Core42 is building an AI supercomputer with 172 million cores which will become operational later this year. The system, Condor Galaxy 3, was announced earlier this year and will have 192 nodes with Cerebras Read more…

Google Announces Sixth-generation AI Chip, a TPU Called Trillium

May 17, 2024

On Tuesday May 14th, Google announced its sixth-generation TPU (tensor processing unit) called Trillium.  The chip, essentially a TPU v6, is the company's latest weapon in the AI battle with GPU maker Nvidia and clou Read more…

ISC 2024 Student Cluster Competition

May 16, 2024

The 2024 ISC 2024 competition welcomed 19 virtual (remote) and eight in-person teams. The in-person teams participated in the conference venue and, while the virtual teams competed using the Bridges-2 supercomputers at t Read more…

ISC 2024 — A Few Quantum Gems and Slides from a Packed QC Agenda

May 22, 2024

If you were looking for quantum computing content, ISC 2024 was a good place to be last week — there were around 20 quantum computing related sessions. QC eve Read more…

Atos Outlines Plans to Get Acquired, and a Path Forward

May 21, 2024

Atos – via its subsidiary Eviden – is the second major supercomputer maker outside of HPE, while others have largely dropped out. The lack of integrators Read more…

Google Announces Sixth-generation AI Chip, a TPU Called Trillium

May 17, 2024

On Tuesday May 14th, Google announced its sixth-generation TPU (tensor processing unit) called Trillium.  The chip, essentially a TPU v6, is the company's l Read more…

Europe’s Race towards Quantum-HPC Integration and Quantum Advantage

May 16, 2024

What an interesting panel, Quantum Advantage — Where are We and What is Needed? While the panelists looked slightly weary — their’s was, after all, one of Read more…

The Future of AI in Science

May 15, 2024

AI is one of the most transformative and valuable scientific tools ever developed. By harnessing vast amounts of data and computational power, AI systems can un Read more…

Some Reasons Why Aurora Didn’t Take First Place in the Top500 List

May 15, 2024

The makers of the Aurora supercomputer, which is housed at the Argonne National Laboratory, gave some reasons why the system didn't make the top spot on the Top Read more…

ISC 2024 Keynote: High-precision Computing Will Be a Foundation for AI Models

May 15, 2024

Some scientific computing applications cannot sacrifice accuracy and will always require high-precision computing. Therefore, conventional high-performance c Read more…

Shutterstock 493860193

Linux Foundation Announces the Launch of the High-Performance Software Foundation

May 14, 2024

The Linux Foundation, the nonprofit organization enabling mass innovation through open source, is excited to announce the launch of the High-Performance Softw Read more…

Synopsys Eats Ansys: Does HPC Get Indigestion?

February 8, 2024

Recently, it was announced that Synopsys is buying HPC tool developer Ansys. Started in Pittsburgh, Pa., in 1970 as Swanson Analysis Systems, Inc. (SASI) by John Swanson (and eventually renamed), Ansys serves the CAE (Computer Aided Engineering)/multiphysics engineering simulation market. Read more…

Nvidia H100: Are 550,000 GPUs Enough for This Year?

August 17, 2023

The GPU Squeeze continues to place a premium on Nvidia H100 GPUs. In a recent Financial Times article, Nvidia reports that it expects to ship 550,000 of its lat Read more…

Comparing NVIDIA A100 and NVIDIA L40S: Which GPU is Ideal for AI and Graphics-Intensive Workloads?

October 30, 2023

With long lead times for the NVIDIA H100 and A100 GPUs, many organizations are looking at the new NVIDIA L40S GPU, which it’s a new GPU optimized for AI and g Read more…

Choosing the Right GPU for LLM Inference and Training

December 11, 2023

Accelerating the training and inference processes of deep learning models is crucial for unleashing their true potential and NVIDIA GPUs have emerged as a game- Read more…

Shutterstock 1606064203

Meta’s Zuckerberg Puts Its AI Future in the Hands of 600,000 GPUs

January 25, 2024

In under two minutes, Meta's CEO, Mark Zuckerberg, laid out the company's AI plans, which included a plan to build an artificial intelligence system with the eq Read more…

AMD MI3000A

How AMD May Get Across the CUDA Moat

October 5, 2023

When discussing GenAI, the term "GPU" almost always enters the conversation and the topic often moves toward performance and access. Interestingly, the word "GPU" is assumed to mean "Nvidia" products. (As an aside, the popular Nvidia hardware used in GenAI are not technically... Read more…

Nvidia’s New Blackwell GPU Can Train AI Models with Trillions of Parameters

March 18, 2024

Nvidia's latest and fastest GPU, codenamed Blackwell, is here and will underpin the company's AI plans this year. The chip offers performance improvements from Read more…

Some Reasons Why Aurora Didn’t Take First Place in the Top500 List

May 15, 2024

The makers of the Aurora supercomputer, which is housed at the Argonne National Laboratory, gave some reasons why the system didn't make the top spot on the Top Read more…

Leading Solution Providers

Contributors

Eyes on the Quantum Prize – D-Wave Says its Time is Now

January 30, 2024

Early quantum computing pioneer D-Wave again asserted – that at least for D-Wave – the commercial quantum era has begun. Speaking at its first in-person Ana Read more…

The GenAI Datacenter Squeeze Is Here

February 1, 2024

The immediate effect of the GenAI GPU Squeeze was to reduce availability, either direct purchase or cloud access, increase cost, and push demand through the roof. A secondary issue has been developing over the last several years. Even though your organization secured several racks... Read more…

Shutterstock 1285747942

AMD’s Horsepower-packed MI300X GPU Beats Nvidia’s Upcoming H200

December 7, 2023

AMD and Nvidia are locked in an AI performance battle – much like the gaming GPU performance clash the companies have waged for decades. AMD has claimed it Read more…

The NASA Black Hole Plunge

May 7, 2024

We have all thought about it. No one has done it, but now, thanks to HPC, we see what it looks like. Hold on to your feet because NASA has released videos of wh Read more…

Intel Plans Falcon Shores 2 GPU Supercomputing Chip for 2026  

August 8, 2023

Intel is planning to onboard a new version of the Falcon Shores chip in 2026, which is code-named Falcon Shores 2. The new product was announced by CEO Pat Gel Read more…

GenAI Having Major Impact on Data Culture, Survey Says

February 21, 2024

While 2023 was the year of GenAI, the adoption rates for GenAI did not match expectations. Most organizations are continuing to invest in GenAI but are yet to Read more…

Atos Outlines Plans to Get Acquired, and a Path Forward

May 21, 2024

Atos – via its subsidiary Eviden – is the second major supercomputer maker outside of HPE, while others have largely dropped out. The lack of integrators Read more…

How the Chip Industry is Helping a Battery Company

May 8, 2024

Chip companies, once seen as engineering pure plays, are now at the center of geopolitical intrigue. Chip manufacturing firms, especially TSMC and Intel, have b Read more…

  • arrow
  • Click Here for More Headlines
  • arrow
HPCwire