Synopsis

Large Photonic Processor Solves Graph Problems

Physics 16, s64
A quantum photonic device can perform some real-world tasks more efficiently than classical computers.
Y. Deng et al. [1]

Quantum computers can outperform their classical counterparts when solving certain computational problems, but the average off-the-shelf laptop is still far better for most tasks. Now Chao-Yang Lu, Jian-Wei Pan, and their colleagues at the University of Science and Technology of China have used a quantum computer based on a photonic network to solve two graph-theory problems [1]. The result extends the list of tasks for which today’s noisy quantum computers offer an advantage over classical computers.

Previously, the team used their photonic processor—a 144-optical-mode interferometer—to solve a problem called Gaussian boson sampling (GBS); see Viewpoint: Quantum Leap for Quantum Primacy. A GBS solution is a prediction—or “sample”—of the probability distribution of photons recorded across the network’s 144 output detectors when those photons are injected into the network one at a time.

This sampling approach links mathematically to graph problems that model pairwise relationships, defined by matrices, between objects. The researchers used their photonic processor to implement search algorithms defined by two such problems. By treating each of the processor’s output ports as a graph vertex and each detected photon as a subgraph vertex, they determined which subgraph mapped to the solution. Their processor arrived at a solution after obtaining 221,891 samples, each of which corresponded to a particular distribution of up to 80 detected photons. Each sample would require 700 seconds on the world’s fastest supercomputer using an exact algorithm.

Previous claims of quantum advantage were challenged by suggestions that the quantum computer was not competing against the best-possible classical algorithm for the task. Whether the team’s quantum processor will still yield an advantage over classical algorithms optimized for solving graph problems is an open question.

–Rachel Berkowitz

Rachel Berkowitz is a Corresponding Editor for Physics Magazine based in Vancouver, Canada.

References

  1. Y. H. Deng et al., “Solving graph problems using Gaussian boson sampling,” Phys. Rev. Lett. 130, 190601 (2023).

Subject Areas

Quantum PhysicsQuantum Information

Related Articles

Positron Emission Tomography Could Be Aided by Entanglement
Medical Physics

Positron Emission Tomography Could Be Aided by Entanglement

The quantum entanglement of photons used in positron emission tomography (PET) scans has been shown to be surprisingly robust, opening prospects for developing quantum-enhanced PET schemes. Read More »

Quantum Chip Cuts Unintended Signals
Quantum Information

Quantum Chip Cuts Unintended Signals

A 25-qubit quantum processor architecture reduces the stray signals that can cause errors and is suitable for scaling up. Read More »

A New Nonlinearity for Superconducting Circuits
Superconductivity

A New Nonlinearity for Superconducting Circuits

Researchers have isolated a high-order term in the behavior of a Josephson junction, which could lead to longer-lived superconducting qubits. Read More »

More Articles