Paper Offers ‘Proof’ of Quantum Advantage on Some Problems

By John Russell

October 18, 2018

Is quantum computing worth all the effort being poured into it or should we just wait for classical computing to catch up? An IBM blog today posed those questions and, you won’t be surprised, offers a firm “it’s worth it” answer. IBM is a long-time quantum pioneer and the blog by Bob Sutor, VP, IBM Q Ecosystem and Strategy, coincides with the publishing of a new IBM-led paper (Quantum advantage with shallow circuits, Science) that offers a proof of quantum computing advantage over classical computer for a class of problems.

The work – by researchers Sergey Bravyi of IBM Research, David Gosset of the University of Waterloo Institute for Quantum Computing, and Robert König of the Institute for Advanced Study and Zentrum Mathematik, Technische Universität München – shows that so-called shallow quantum circuits are inherently more powerful than classical counterparts on some tasks. This has added practical importance given the constraints of today’s small, noisy quantum computers, which can only handle shallow circuits.

The researchers write: “Can constant-depth quantum circuits solve a computational problem that constant-depth classical circuits cannot? [Or] put differently, we ask whether constant-time parallel quantum algorithms are more powerful than their classical probabilistic counterparts. We show that the answer to the above question is YES, even if the quantum circuit is composed of nearest-neighbor gates acting on a 2D grid whereas the only restriction on the constant-depth classical (probabilistic) circuit is having a bounded fan-in.

“In particular, the gates in the classical circuit may be long-range (i.e., they need not be geometrically local in 2D or otherwise) and may have unbounded fan-out. We emphasize that our result constitutes a provable separation and does not rely on any conjectures or assumptions concerning complexity classes. Formally, our result implies that there is a search (relational) problem solved by SQCs but not by NC0 circuits, even if we allow the classical circuit access to random input bits drawn from an arbitrary distribution depending on the input size.”

Scientists prove there are certain problems that require only a fixed circuit depth when done on a quantum computer no matter how the number of inputs increase. On a classical computer, these same problems require the circuit depth to grow larger. Source: IBM

Leaving aside the details of their work for a moment, the proof opens new avenues for algorithm and application development using their approach. For quite some time there has been a “where are the new algorithms and show me the applications” vibe among many quantum watchers even as industry, academia, and governments ramped up quantum research efforts. Clearly, quantum computing remains in a nascent stage; that said, IBM’s paper is step forward.

Sutor framed the challenge quite nicely in his blog:

“In 1994 Peter Shor formulated his eponymous algorithm that demonstrated how to factor integers on a quantum computer almost exponentially faster than any known method on a classical computer. This is getting a lot of attention because some people are getting concerned that we may be able to break prime-factor-based encryption like RSA much faster on a quantum computer than the thousands of years it would take using known classical methods. However, people skip several elements of the fine print.

“First, we would need millions and millions of extremely high quality qubits with low error rates and long coherence time for this to work. Today we have 50.

“Second, there’s the bit about “faster than any known method on a classical computer.” Since we do not know an efficient way of factoring arbitrary large numbers on classical computers, this appears to be a hard problem. It’s not proved to be a hard problem. If someone next week comes up with an amazing new approach using a classical computer that factors as fast as Shor’s might, then the conjecture of it being hard is false. We just don’t know.

“Is everything like that? Are we just waiting for people to be more clever on classical computers so that any hoped-for quantum computing advantage might disappear? The answer is no. Quantum computers really are faster at some things. We can prove it. This is important.”

For many in the HPC community much about quantum computing remains unfamiliar. Most of us think about von Neumann architectures and gates etched in silicon and data moving through them. Quantum chips are almost the reverse. Qubits, the registers of the data if you will, are ‘etched’ in silicon and you operate on them by applying external signals, the gates, to them.

IBM scientist Bravyi briefly described the shallow circuits at the heart of the latest work, “A quantum circuit is a sequence of elementary operations that we call gates. Each gate can touch only one or two quantum bits (qubits). Qubits start out as 0s or 1s, we perform gates on them involving superposition and entanglement, and then we measure every qubit. Once measured, we again have 0s and 1s.”

“Shallow quantum circuits are those in which each qubit participates only in a few gates before it has been measured. The maximum number of gates per qubit is called the depth of a circuit. Near-term quantum devices can implement only shallow (constant-depth) circuits because qubits quickly decohere and become chaotic,” he said. (Below is a schematic diagram of the quantum circuit researchers propose taken from the paper.)

Bravyi emphasized the broad impact of the team’s work. “The research in this paper conclusively shows that quantum computers can do some things better than classical computers can. The proof is the first demonstration of unconditional separation between quantum and classical algorithms, albeit in the special case of constant-depth computations.

“In practice, short depth circuits are part of the implementations of algorithms, so this result does not specifically say how and where quantum computers might be better for particular business problems. But it is a foundational element that other scientists will be able to experiment with, soon.”

“The IBM Q team is preparing a demonstration of the algorithm on one of its current quantum computers, to be ready in the coming weeks. The goal of the demo, using Qiskit in a Jupyter notebook, is to start to test the circuits with simulators. By using a noisy simulator we learn how such circuits will eventually run on actual hardware. All this goes to giving us fundamental knowledge which helps us advance how we build algorithms and tune the hardware,” said Bravyi.

IBM was the first to provide widespread access to a quantum computing development platform via the IBM Q cloud platform, launched in 2016. Since then, IBM reports more than 100,000 people have used IBM Q.

Link to blog: https://www.ibm.com/blogs/research/2018/10/quantum-advantage-2/

Link to Sergey Bravyi video: https://www.youtube.com/watch?v=xogOLp36GlA

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!

Intel’s Vision Advantage: Chips Are Available Off-the-Shelf

April 11, 2024

The chip market is facing a crisis: chip development is now concentrated in the hands of the few. A confluence of events this week reminded us how few chips are available off the shelf, a concern raised at many recent Read more…

The VC View: Quantonation’s Deep Dive into Funding Quantum Start-ups

April 11, 2024

Yesterday Quantonation — which promotes itself as a one-of-a-kind venture capital (VC) company specializing in quantum science and deep physics  — announced its second fund targeting €200 million. The very idea th Read more…

Nvidia’s GTC Is the New Intel IDF

April 9, 2024

After many years, Nvidia's GPU Technology Conference (GTC) was back in person and has become the conference for those who care about semiconductors and AI. In a way, Nvidia is the new Intel IDF, the hottest chip show Read more…

Google Announces Homegrown ARM-based CPUs 

April 9, 2024

Google sprang a surprise at the ongoing Google Next Cloud conference by introducing its own ARM-based CPU called Axion, which will be offered to customers in its cloud service.  Google claimed the CPU is based on cut Read more…

Computational Chemistry Needs To Be Sustainable, Too

April 8, 2024

A diverse group of computational chemists is encouraging the research community to embrace a sustainable software ecosystem. That's the message behind a recent perspective article published in the Journal of Chemical Read more…

U.S. 2024/25 Science Budgets Taking a Hit

April 8, 2024

In case you missed it, fiscal 2024/25 U.S. science budgets seem likely to take big hits despite Congressional talk of increased support, reports the American Institute of Physics (AIP) FYI policy tracking coverage. AIP F Read more…

Intel’s Vision Advantage: Chips Are Available Off-the-Shelf

April 11, 2024

The chip market is facing a crisis: chip development is now concentrated in the hands of the few. A confluence of events this week reminded us how few chips Read more…

The VC View: Quantonation’s Deep Dive into Funding Quantum Start-ups

April 11, 2024

Yesterday Quantonation — which promotes itself as a one-of-a-kind venture capital (VC) company specializing in quantum science and deep physics  — announce Read more…

Nvidia’s GTC Is the New Intel IDF

April 9, 2024

After many years, Nvidia's GPU Technology Conference (GTC) was back in person and has become the conference for those who care about semiconductors and AI. I Read more…

Google Announces Homegrown ARM-based CPUs 

April 9, 2024

Google sprang a surprise at the ongoing Google Next Cloud conference by introducing its own ARM-based CPU called Axion, which will be offered to customers in it Read more…

Computational Chemistry Needs To Be Sustainable, Too

April 8, 2024

A diverse group of computational chemists is encouraging the research community to embrace a sustainable software ecosystem. That's the message behind a recent Read more…

Hyperion Research: Eleven HPC Predictions for 2024

April 4, 2024

HPCwire is happy to announce a new series with Hyperion Research  - a fact-based market research firm focusing on the HPC market. In addition to providing mark Read more…

Google Making Major Changes in AI Operations to Pull in Cash from Gemini

April 4, 2024

Over the last week, Google has made some under-the-radar changes, including appointing a new leader for AI development, which suggests the company is taking its Read more…

Parallel Perspectives: HPC Internships Educate and Inspire 

April 4, 2024

As an undergraduate Sophomore at the University of Chicago, Joey Lin embarked on a journey to explore how an internship opportunity involving high-performanc 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…

DoD Takes a Long View of Quantum Computing

December 19, 2023

Given the large sums tied to expensive weapon systems – think $100-million-plus per F-35 fighter – it’s easy to forget the U.S. Department of Defense is a 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…

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…

Intel’s Server and PC Chip Development Will Blur After 2025

January 15, 2024

Intel's dealing with much more than chip rivals breathing down its neck; it is simultaneously integrating a bevy of new technologies such as chiplets, artificia Read more…

Baidu Exits Quantum, Closely Following Alibaba’s Earlier Move

January 5, 2024

Reuters reported this week that Baidu, China’s giant e-commerce and services provider, is exiting the quantum computing development arena. Reuters reported � 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…

Shutterstock 1179408610

Google Addresses the Mysteries of Its Hypercomputer 

December 28, 2023

When Google launched its Hypercomputer earlier this month (December 2023), the first reaction was, "Say what?" It turns out that the Hypercomputer is Google's t Read more…

Leading Solution Providers

Contributors

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…

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…

China Is All In on a RISC-V Future

January 8, 2024

The state of RISC-V in China was discussed in a recent report released by the Jamestown Foundation, a Washington, D.C.-based think tank. The report, entitled "E 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…

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…

Intel Won’t Have a Xeon Max Chip with New Emerald Rapids CPU

December 14, 2023

As expected, Intel officially announced its 5th generation Xeon server chips codenamed Emerald Rapids at an event in New York City, where the focus was really o 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…

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…

  • arrow
  • Click Here for More Headlines
  • arrow
HPCwire