Synopsis: A Possible Quantum Computing Boost 

A hybrid quantum-classical computing algorithm could solve a basic computer science problem faster than a classical computer.
Synopsis figure
V. Dunjko/Leiden University

As companies race to build bigger quantum computers, it’s still unclear what near-term devices made of 100 qubits or less will be good for. Searching for applications, researchers are developing algorithms where quantum computing could boost performance. Now, Vedran Dunjko of Leiden University in the Netherlands and colleagues show that a small quantum computer can speed up an algorithm for solving the so-called 3SAT problem, a basic problem that is difficult for classical computers.

The 3SAT problem is a type of basic logic puzzle that tries to find values for some number of Boolean variables in an equation such that given combinations of groups of three return a true value. These problems show up in optimization algorithms such as scheduling and planning tasks, as well as statistical physics. However, classical computers likely cannot solve them efficiently with brute-force methods.

The researchers based their quantum method on a classical solution for solving 3SAT problems known as Schöning’s algorithm. They found that the quantum algorithm boosts performance only if the number of Boolean variables does not exceed a threshold that depends on the number of qubits in the computer. Thus they propose a quantum-classical hybrid algorithm that first reduces the number of variables on a classical computer and then switches to a quantum computer when the number of variables reaches the threshold. However, the researchers point out that the algorithm assumes error-corrected qubits, which hardware developers have not achieved yet. To implement the algorithm on near-term devices, the researchers say it would need to be further tailored to specific hardware.

This research is published in Physical Review Letters.

–Sophia Chen

Sophia Chen is a freelance science writer based in Tucson, Arizona.


Features

More Features »

Announcements

More Announcements »

Subject Areas

Quantum Information

Previous Synopsis

Interdisciplinary Physics

How Walkers Avoid Collisions

Read More »

Next Synopsis

Materials Science

Fresh Light on Nonthermal Electrons

Read More »

Related Articles

Synopsis: Making Quantum Cryptography Safe and Practical
Quantum Information

Synopsis: Making Quantum Cryptography Safe and Practical

A theoretical study suggests that “continuous variable” quantum key distribution—an approach to quantum cryptography compatible with telecom networks—could be made absolutely secure against hacking. Read More »

Synopsis: Counting Phonons One by One
Quantum Information

Synopsis: Counting Phonons One by One

A device enables the detection of single quanta of sound, a step towards using them in quantum technologies. Read More »

Synopsis: Entangled Photon Source Ticks All Boxes
Quantum Physics

Synopsis: Entangled Photon Source Ticks All Boxes

A quantum-dot-based device combines all of the attributes necessary for producing a reliable source of entangled photons for quantum information applications.  Read More »

More Articles