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!

Senegal Prepares to Take Delivery of Atos Supercomputer

January 16, 2019

In just a few months time, Senegal will be operating the second largest HPC system in sub-Saharan Africa. The Minister of Higher Education, Research and Innovation Mary Teuw Niane made the announcement on Monday (Jan. 14 Read more…

By Tiffany Trader

Google Cloud Platform Extends GPU Instance Options

January 16, 2019

If it's Nvidia GPUs you're after to power your AI/HPC/visualization workload, Google Cloud has them, now claiming "broadest GPU availability." Each of the three big public cloud vendors has by turn touted the latest and Read more…

By Tiffany Trader

A Big Data Journey While Seeking to Catalog our Universe

January 16, 2019

It turns out, astronomers have lots of photos of the sky but seek knowledge about what the photos mean. Sound familiar? Big data problems are often characterized as transforming data into insights – which is exactly wh Read more…

By James Reinders

HPE Extreme Performance Solutions

HPE Systems With Intel Omni-Path: Architected for Value and Accessible High-Performance Computing

Today’s high-performance computing (HPC) and artificial intelligence (AI) users value high performing clusters. And the higher the performance that their system can deliver, the better. Read more…

IBM Accelerated Insights

Resource Management in the Age of Artificial Intelligence

New challenges demand fresh approaches

Fueled by GPUs, big data, and rapid advances in software, the AI revolution is upon us. Read more…

STAC Floats ML Benchmark for Financial Services Workloads

January 16, 2019

STAC (Securities Technology Analysis Center) recently released an ‘exploratory’ benchmark for machine learning which it hopes will evolve into a firm benchmark or suite of benchmarking tools to compare the performanc Read more…

By John Russell

A Big Data Journey While Seeking to Catalog our Universe

January 16, 2019

It turns out, astronomers have lots of photos of the sky but seek knowledge about what the photos mean. Sound familiar? Big data problems are often characterize Read more…

By James Reinders

STAC Floats ML Benchmark for Financial Services Workloads

January 16, 2019

STAC (Securities Technology Analysis Center) recently released an ‘exploratory’ benchmark for machine learning which it hopes will evolve into a firm benchm Read more…

By John Russell

IBM Quantum Update: Q System One Launch, New Collaborators, and QC Center Plans

January 10, 2019

IBM made three significant quantum computing announcements at CES this week. One was introduction of IBM Q System One; it’s really the integration of IBM’s Read more…

By John Russell

IBM’s New Global Weather Forecasting System Runs on GPUs

January 9, 2019

Anyone who has checked a forecast to decide whether or not to pack an umbrella knows that weather prediction can be a mercurial endeavor. It is a Herculean task: the constant modeling of incredibly complex systems to a high degree of accuracy at a local level within very short spans of time. Read more…

By Oliver Peckham

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

The Deep500 – Researchers Tackle an HPC Benchmark for Deep Learning

January 7, 2019

How do you know if an HPC system, particularly a larger-scale system, is well-suited for deep learning workloads? Today, that’s not an easy question to answer Read more…

By John Russell

HPCwire Awards Highlight Supercomputing Achievements in the Sciences

January 3, 2019

In November at SC18 in Dallas, HPCwire Readers’ and Editors’ Choice awards program commemorated its 15th year of honoring achievement in HPC, with categories ranging from Best Use of AI to the Workforce Diversity Leadership Award and recipients across a wide variety of industrial and research sectors. Read more…

By the Editorial Team

White House Top Science Post Filled After Two-Year Vacancy

January 3, 2019

Half-way into Trump's term, the Senate has confirmed a director for the Office of Science and Technology Policy (OSTP), the agency that coordinates science poli Read more…

By Tiffany Trader

Quantum Computing Will Never Work

November 27, 2018

Amid the gush of money and enthusiastic predictions being thrown at quantum computing comes a proposed cold shower in the form of an essay by physicist Mikhail Read more…

By John Russell

Cray Unveils Shasta, Lands NERSC-9 Contract

October 30, 2018

Cray revealed today the details of its next-gen supercomputing architecture, Shasta, selected to be the next flagship system at NERSC. We've known of the code-name "Shasta" since the Argonne slice of the CORAL project was announced in 2015 and although the details of that plan have changed considerably, Cray didn't slow down its timeline for Shasta. Read more…

By Tiffany Trader

Summit Supercomputer is Already Making its Mark on Science

September 20, 2018

Summit, now the fastest supercomputer in the world, is quickly making its mark in science – five of the six finalists just announced for the prestigious 2018 Read more…

By John Russell

AMD Sets Up for Epyc Epoch

November 16, 2018

It’s been a good two weeks, AMD’s Gary Silcott and Andy Parma told me on the last day of SC18 in Dallas at the restaurant where we met to discuss their show news and recent successes. Heck, it’s been a good year. Read more…

By Tiffany Trader

US Leads Supercomputing with #1, #2 Systems & Petascale Arm

November 12, 2018

The 31st Supercomputing Conference (SC) - commemorating 30 years since the first Supercomputing in 1988 - kicked off in Dallas yesterday, taking over the Kay Ba Read more…

By Tiffany Trader

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

Contract Signed for New Finnish Supercomputer

December 13, 2018

After the official contract signing yesterday, configuration details were made public for the new BullSequana system that the Finnish IT Center for Science (CSC Read more…

By Tiffany Trader

House Passes $1.275B National Quantum Initiative

September 17, 2018

Last Thursday the U.S. House of Representatives passed the National Quantum Initiative Act (NQIA) intended to accelerate quantum computing research and developm Read more…

By John Russell

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

Nvidia’s Jensen Huang Delivers Vision for the New HPC

November 14, 2018

For nearly two hours on Monday at SC18, Jensen Huang, CEO of Nvidia, presented his expansive view of the future of HPC (and computing in general) as only he can do. Animated. Backstopped by a stream of data charts, product photos, and even a beautiful image of supernovae... Read more…

By John Russell

HPE No. 1, IBM Surges, in ‘Bucking Bronco’ High Performance Server Market

September 27, 2018

Riding healthy U.S. and global economies, strong demand for AI-capable hardware and other tailwind trends, the high performance computing server market jumped 28 percent in the second quarter 2018 to $3.7 billion, up from $2.9 billion for the same period last year, according to industry analyst firm Hyperion Research. Read more…

By Doug Black

HPC Reflections and (Mostly Hopeful) Predictions

December 19, 2018

So much ‘spaghetti’ gets tossed on walls by the technology community (vendors and researchers) to see what sticks that it is often difficult to peer through Read more…

By John Russell

Intel Confirms 48-Core Cascade Lake-AP for 2019

November 4, 2018

As part of the run-up to SC18, taking place in Dallas next week (Nov. 11-16), Intel is doling out info on its next-gen Cascade Lake family of Xeon processors, specifically the “Advanced Processor” version (Cascade Lake-AP), architected for high-performance computing, artificial intelligence and infrastructure-as-a-service workloads. Read more…

By Tiffany Trader

Germany Celebrates Launch of Two Fastest Supercomputers

September 26, 2018

The new high-performance computer SuperMUC-NG at the Leibniz Supercomputing Center (LRZ) in Garching is the fastest computer in Germany and one of the fastest i Read more…

By Tiffany Trader

Houston to Field Massive, ‘Geophysically Configured’ Cloud Supercomputer

October 11, 2018

Based on some news stories out today, one might get the impression that the next system to crack number one on the Top500 would be an industrial oil and gas mon Read more…

By Tiffany Trader

Microsoft to Buy Mellanox?

December 20, 2018

Networking equipment powerhouse Mellanox could be an acquisition target by Microsoft, according to a published report in an Israeli financial publication. Microsoft has reportedly gone so far as to engage Goldman Sachs to handle negotiations with Mellanox. Read more…

By Doug Black

The Deep500 – Researchers Tackle an HPC Benchmark for Deep Learning

January 7, 2019

How do you know if an HPC system, particularly a larger-scale system, is well-suited for deep learning workloads? Today, that’s not an easy question to answer Read more…

By John Russell

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