Source-linked AI summary
Experimental Quantum Computing to Solve Systems of Linear Equations
X. -D. Cai, Christian Weedbrook, Z. -E. Su, M. -C. Chen, Mile Gu, M. -J. Zhu, L. Li, N. -L. Liu, Chao-Yang Lu, Jian-Wei Pan
TL;DR
Large linear systems can challenge classical computation because solving N equations requires time proportional to N, while a quantum algorithm targets O(log(N)) time in supported settings. This paper demonstrates the simplest meaningful instance by solving 2 × 2 systems with four photonic qubits and four controlled logic gates, achieving output fidelities from 0.825 to 0.993.
Problem
Classical algorithms for systems of N linear equations require time proportional to N, motivating quantum approaches that can estimate solution-related properties in O(log(N)) time.
Method
The experiment implements every subroutine of the linear-system quantum algorithm in a linear optical network using four photonic qubits and four controlled logic gates.
Results
Output-state fidelities for three input vectors were 0.993(3), 0.825(13), and 0.836(16), respectively.
Takeaways & Limitations
The experiment demonstrates the working principle of a quantum algorithm for solving small systems of linear equations and implements all of its core subroutines.
Takeaways & Limitations
The experiment remains limited by a probabilistic single-photon source and inefficient detectors, constraining larger-scale implementations.
Abstract
from arXiv · showhide
Solving linear systems of equations is ubiquitous in all areas of science and engineering. With rapidly growing data sets, such a task can be intractable for classical computers, as the best known classical algorithms require a time proportional to the number of variables N. A recently proposed quantum algorithm shows that quantum computers could solve linear systems in a time scale of order log(N), giving an exponential speedup over classical computers. Here we realize the simplest instance of this algorithm, solving 2*2 linear equations for various input vectors on a quantum computer. We use four quantum bits and four controlled logic gates to implement every subroutine required, demonstrating the working principle of this algorithm.