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 industy updates delivered to you every week!

RIKEN Post-K Supercomputer Named After Japan’s Tallest Peak

May 23, 2019

May 23 -- RIKEN President Hiroshi Matsumoto announced that the successor to the K computer will be named Fugaku, another name for Mount Fuji, which is the tallest mountain peak in Japan. Supercomputer Fugaku, developed b Read more…

By Tiffany Trader

Cray’s Emerging Market & Technology Director Arti Garg Peers Around HPC/AI Corner

May 23, 2019

In her position as emerging market and technology director at Cray, Arti Garg doesn't just have a front-row seat to the future of computing, she plays an active role in making that future happen. Key to Garg's role is understanding how deep learning scientists are using state-of-the-art HPC infrastructures and figuring out how to push those limits further. Read more…

By Tiffany Trader

Combining Machine Learning and Supercomputing to Ferret out Phishing Attacks

May 23, 2019

The relentless ingenuity that drives cyber hacking is a global engine that knows no rest. Anyone with a laptop and run-of-the-mill computer smarts can buy or rent a phishing kit and start attacking – or it can be done Read more…

By Doug Black

HPE Extreme Performance Solutions

HPE and Intel® Omni-Path Architecture: How to Power a Cloud

Learn how HPE and Intel® Omni-Path Architecture provide critical infrastructure for leading Nordic HPC provider’s HPCFLOW cloud service.

For decades, HPE has been at the forefront of high-performance computing, and we’ve powered some of the fastest and most robust supercomputers in the world. Read more…

IBM Accelerated Insights

Who’s Driving Your Car?

Delivering a fully autonomous driving (AD) vehicle remains a key priority for both manufacturers and technology firms (“firms”). However, passenger safety is now a top-of-mind concern due in great part, to fatalities resulting from driving tests over the past years. Read more…

TACC’s Upgraded Ranch Data Storage System Debuts New Features, Exabyte Potential

May 22, 2019

There's a joke attributed to comedian Steven Wright that goes, "You can't have everything. Where would you put it?" Users of advanced computing can likely relate to this. The exponential growth of data poses a steep challenge to efforts for its reliable storage. For over 12 years, the Ranch system at the Texas Advanced Computing Center... Read more…

By Jorge Salazar, TACC

Cray’s Emerging Market & Technology Director Arti Garg Peers Around HPC/AI Corner

May 23, 2019

In her position as emerging market and technology director at Cray, Arti Garg doesn't just have a front-row seat to the future of computing, she plays an active role in making that future happen. Key to Garg's role is understanding how deep learning scientists are using state-of-the-art HPC infrastructures and figuring out how to push those limits further. Read more…

By Tiffany Trader

Combining Machine Learning and Supercomputing to Ferret out Phishing Attacks

May 23, 2019

The relentless ingenuity that drives cyber hacking is a global engine that knows no rest. Anyone with a laptop and run-of-the-mill computer smarts can buy or re Read more…

By Doug Black

Cray – and the Cray Brand – to Be Positioned at Tip of HPE’s HPC Spear

May 22, 2019

More so than with most acquisitions of this kind, HPE’s purchase of Cray for $1.3 billion, announced last week, seems to have elements of that overused, often Read more…

By Doug Black and Tiffany Trader

HPE to Acquire Cray for $1.3B

May 17, 2019

Venerable supercomputer pioneer Cray Inc. will be acquired by Hewlett Packard Enterprise for $1.3 billion under a definitive agreement announced this morning. T Read more…

By Doug Black & Tiffany Trader

Deep Learning Competitors Stalk Nvidia

May 14, 2019

There is no shortage of processing architectures emerging to accelerate deep learning workloads, with two more options emerging this week to challenge GPU leader Nvidia. First, Intel researchers claimed a new deep learning record for image classification on the ResNet-50 convolutional neural network. Separately, Israeli AI chip startup Hailo.ai... Read more…

By George Leopold

CCC Offers Draft 20-Year AI Roadmap; Seeks Comments

May 14, 2019

Artificial Intelligence in all its guises has captured much of the conversation in HPC and general computing today. The White House, DARPA, IARPA, and Departmen Read more…

By John Russell

Cascade Lake Shows Up to 84 Percent Gen-on-Gen Advantage on STAC Benchmarking

May 13, 2019

The Securities Technology Analysis Center (STAC) issued a report Friday comparing the performance of Intel's Cascade Lake processors with previous-gen Skylake u Read more…

By Tiffany Trader

Nvidia Claims 6000x Speed-Up for Stock Trading Backtest Benchmark

May 13, 2019

A stock trading backtesting algorithm used by hedge funds to simulate trading variants has received a massive, GPU-based performance boost, according to Nvidia, Read more…

By Doug Black

Cray, AMD to Extend DOE’s Exascale Frontier

May 7, 2019

Cray and AMD are coming back to Oak Ridge National Laboratory to partner on the world’s largest and most expensive supercomputer. The Department of Energy’s Read more…

By Tiffany Trader

Graphene Surprises Again, This Time for Quantum Computing

May 8, 2019

Graphene is fascinating stuff with promise for use in a seeming endless number of applications. This month researchers from the University of Vienna and Institu Read more…

By John Russell

Why Nvidia Bought Mellanox: ‘Future Datacenters Will Be…Like High Performance Computers’

March 14, 2019

“Future datacenters of all kinds will be built like high performance computers,” said Nvidia CEO Jensen Huang during a phone briefing on Monday after Nvidia revealed scooping up the high performance networking company Mellanox for $6.9 billion. Read more…

By Tiffany Trader

It’s Official: Aurora on Track to Be First US Exascale Computer in 2021

March 18, 2019

The U.S. Department of Energy along with Intel and Cray confirmed today that an Intel/Cray supercomputer, "Aurora," capable of sustained performance of one exaf Read more…

By Tiffany Trader

ClusterVision in Bankruptcy, Fate Uncertain

February 13, 2019

ClusterVision, European HPC specialists that have built and installed over 20 Top500-ranked systems in their nearly 17-year history, appear to be in the midst o Read more…

By Tiffany Trader

Intel Reportedly in $6B Bid for Mellanox

January 30, 2019

The latest rumors and reports around an acquisition of Mellanox focus on Intel, which has reportedly offered a $6 billion bid for the high performance interconn Read more…

By Doug Black

Looking for Light Reading? NSF-backed ‘Comic Books’ Tackle Quantum Computing

January 28, 2019

Still baffled by quantum computing? How about turning to comic books (graphic novels for the well-read among you) for some clarity and a little humor on QC. The Read more…

By John Russell

Deep Learning Competitors Stalk Nvidia

May 14, 2019

There is no shortage of processing architectures emerging to accelerate deep learning workloads, with two more options emerging this week to challenge GPU leader Nvidia. First, Intel researchers claimed a new deep learning record for image classification on the ResNet-50 convolutional neural network. Separately, Israeli AI chip startup Hailo.ai... Read more…

By George Leopold

Leading Solution Providers

SC 18 Virtual Booth Video Tour

Advania @ SC18 AMD @ SC18
ASRock Rack @ SC18
DDN Storage @ SC18
HPE @ SC18
IBM @ SC18
Lenovo @ SC18 Mellanox Technologies @ SC18
NVIDIA @ SC18
One Stop Systems @ SC18
Oracle @ SC18 Panasas @ SC18
Supermicro @ SC18 SUSE @ SC18 TYAN @ SC18
Verne Global @ SC18

The Case Against ‘The Case Against Quantum Computing’

January 9, 2019

It’s not easy to be a physicist. Richard Feynman (basically the Jimi Hendrix of physicists) once said: “The first principle is that you must not fool yourse Read more…

By Ben Criger

Deep500: ETH Researchers Introduce New Deep Learning Benchmark for HPC

February 5, 2019

ETH researchers have developed a new deep learning benchmarking environment – Deep500 – they say is “the first distributed and reproducible benchmarking s Read more…

By John Russell

IBM Bets $2B Seeking 1000X AI Hardware Performance Boost

February 7, 2019

For now, AI systems are mostly machine learning-based and “narrow” – powerful as they are by today's standards, they're limited to performing a few, narro Read more…

By Doug Black

Arm Unveils Neoverse N1 Platform with up to 128-Cores

February 20, 2019

Following on its Neoverse roadmap announcement last October, Arm today revealed its next-gen Neoverse microarchitecture with compute and throughput-optimized si Read more…

By Tiffany Trader

Intel Launches Cascade Lake Xeons with Up to 56 Cores

April 2, 2019

At Intel's Data-Centric Innovation Day in San Francisco (April 2), the company unveiled its second-generation Xeon Scalable (Cascade Lake) family and debuted it Read more…

By Tiffany Trader

Announcing four new HPC capabilities in Google Cloud Platform

April 15, 2019

When you’re running compute-bound or memory-bound applications for high performance computing or large, data-dependent machine learning training workloads on Read more…

By Wyatt Gorman, HPC Specialist, Google Cloud; Brad Calder, VP of Engineering, Google Cloud; Bart Sano, VP of Platforms, Google Cloud

Nvidia Claims 6000x Speed-Up for Stock Trading Backtest Benchmark

May 13, 2019

A stock trading backtesting algorithm used by hedge funds to simulate trading variants has received a massive, GPU-based performance boost, according to Nvidia, Read more…

By Doug Black

In Wake of Nvidia-Mellanox: Xilinx to Acquire Solarflare

April 25, 2019

With echoes of Nvidia’s recent acquisition of Mellanox, FPGA maker Xilinx has announced a definitive agreement to acquire Solarflare Communications, provider Read more…

By Doug Black

  • arrow
  • Click Here for More Headlines
  • arrow
Do NOT follow this link or you will be banned from the site!
Share This