Skip to content

Quantum Supremacy: Quantum Hybrid HHL Algorithm for Solving a System of Linear Equation


A team of researchers has realized hybrid quantum algorithm for solving a linear system of equations with exponential speedup that utilizes quantum phase estimation, one of the exemplary core protocols for quantum computing.

Terra Quantum AG, which is a Swiss based Quantum Tech startup, has developed this algorithm.

Their experiment carried out on superconducting IBMQ devices reveals the main shortcomings of the present quantum processors, which must be surpassed in order to boost quantum data processing via phase estimation. The developed algorithm demonstrates quantum supremacy and holds high promise to meet practically relevant challenges.

They implemented the quantum hybrid HHL algorithm solving a system of linear equation by the fast matrix inversion. The matrix, in turn, is approximated by the unitary transformation, which was dictated by the se- quences of single-qubit rotations and CNOT gates. The size of the linear system grows exponentially with the increasing number of qubits. Using the IBM state-of-art 53 qubits processor, one inverts the 1015 matrix, which is far beyond the capabilities of the modern supercomputers.

The team probed the algorithm on the simulator with embedded noise model and on the real IBMQ QPUs with 5, 15 and 20 qubits, and showed that the cross entropy fidelity FXEB can serve as an adequate performance metric for the real quantum algorithm. Furthermore, the researchers estimated the fidelity level of the algorithm implemented on a next- generation 50+ qubit processors and found that the system cannot be solved with the QPUs fidelity on a super-computer in less than a few centuries neither directly nor by using special techniques such as a high-performance simulation of a quantum circuit. Observed exponential scaling in the equal-fidelity classical computation runtime indicates that NISQ devices, which exploit only polynomial time resources, exponentially outperform existing classical analogues.

These experimental results and theoretical estimates hold high potential for guiding researchers in solving large systems of linear equations utilizing state-of-the-art NISQ computers. The team intend to probe the H-HHL algorithm on the cutting edge low-noise QPUs and collect experimental data in order to give a chance to the future computational devices to verify the fidelity.

They envision that the planned experiment will stimulate major players of the quantum computing industry to demonstrate the hardware actually achieving the quantum supremacy.