Synopsis: Making Hard Problems for Quantum Computers

Researchers have developed a computer algorithm that doesn’t solve problems but instead creates them for the purpose of evaluating quantum computers.
Synopsis figure
Courtesy of D-Wave Systems Inc.

The desire for quantum computers stems from their potential to solve certain hard problems faster than classical computers. But those bragging rights haven’t actually been earned yet, as no experiment has shown this presumed speedup. Researchers from the University of Southern California, Los Angeles, and the Complutense University of Madrid, Spain, have devised an algorithm that generates extra hard problems that could offer quantum computers the chance to prove their worth.

The problems that the team focused on belong to the general class of optimization problems. The main example is the Ising model, which describes the interaction of a large number of spins within a lattice. The goal is to find the ground state, which is the orientation of spins that minimizes the interaction energy. The problem is computationally hard because there are many local minima (pseudo-ground-states) that can fool a search algorithm.

Quantum computers—specifically so-called quantum annealers—offer promise for efficiently solving the Ising model and other optimization problems by using quantum superposition to sample all possible minima simultaneously. To test this potential, researchers have randomly generated Ising-type problems tailored to the size of current quantum annealers, such as the 512-qubit D-Wave Two processor. Unfortunately, for this relatively small size, quantum annealers do not show a significant improvement over classical counterparts. In the new study, the researchers propose a way of identifying harder problems so that differences become starker. They have devised an algorithm that starts with a random Ising-type problem and then optimizes the hardness, which is defined by the solution time for a classical computer. The team showed that they could increase the hardness by more than 2 orders of magnitude.

This research is published in Physical Review A.

–Michael Schirber

Michael Schirber is a Corresponding Editor for Physics based in Lyon, France.


More Features »


More Announcements »

Subject Areas

Quantum Information

Previous Synopsis

Statistical Physics

In, Yet Out of Equilibrium

Read More »

Next Synopsis

Chemical Physics

Water Under Confinement

Read More »

Related Articles

Viewpoint: Record Distance for Quantum Cryptography

Viewpoint: Record Distance for Quantum Cryptography

An optical-fiber-based quantum cryptography scheme works over a record distance of 421 km and at much faster rates than previous long-distance demonstrations. Read More »

Focus: Entangled Photons Sneak through Hole Unscathed

Focus: Entangled Photons Sneak through Hole Unscathed

The fragile quantum state of a pair of entangled photons can be protected when the photons pass through a nanoscale hole, which may be useful in future light-based computing. Read More »

Viewpoint: Cold Atoms Bear a Quantum Scar
Quantum Information

Viewpoint: Cold Atoms Bear a Quantum Scar

Theorists attribute the unexpectedly slow thermalization of cold atoms seen in recent experiments to an effect called quantum many-body scarring. Read More »

More Articles