Solving linear systems of equations is an essential component in science and technology, including in many machine learning algorithms. Existing quantum algorithms have demonstrated large speedups in solving linear systems, but the required quantum resources are not available on near- term quantum devices.
Researchers at California Institute of Technology have studied potential near-term quantum algorithms for linear systems of equations. They investigated the use of variational algorithms for solving Ax = b and analyzed their optimization landscapes. They discovered that a wide range of variational algorithms designed to avoid barren plateaus, such as properly-initialized imaginary time evolution and adiabatic-inspired optimization, still suffer from a fundamentally different plateau problem.
To circumvent this issue, they designed a potentially near-term adaptive alternating algorithm based on a core idea: the classical combination of variational quantum states. The team has conducted numerical experiments solving linear systems as large as 2300 × 2300 by considering special systems that can be simulated efficiently on a classical computer. These experiments demonstrated the algorithm’s ability to scale to system sizes within reach in near-term quantum devices of about 100-300 qubits. (Caltech)