Willie Aboumrad and Dominic Widdows from quantum company IonQ have developed Mod2VQLS, a hybrid classical-quantum system for solving binary-valued linear equations using quantum computers. The system includes a new circuit design for implementing matrix multiplication modulo 2 and a variational circuit to be optimized.
The classical components include an optimizer and a controller. Initial numerical experiments indicate that Mod2VQLS is on par with the block Wiedemann algorithm, the best-known solution for this problem. The system has potential applications in various fields, including solving systems of simultaneous linear equations and recent record-breaking RSA factorization calculations.
Introduction to Mod2VQLS: A Variational Quantum Algorithm
Willie Aboumrad and Dominic Widdows from IonQ Inc. have developed a system for solving binary-valued linear equations using quantum computers. The system, named Mod2VQLS (Modulo 2 Variational Quantum Linear Solver), is a classical-quantum hybrid. It is the first of its kind, and its design includes a new circuit design for implementing matrix multiplication modulo 2 and a variational circuit to be optimized. The classical components include the optimizer, which measures the cost function and updates the quantum parameters for each iteration, and the controller that runs the quantum job and classical optimizer iterations.
Mod2VQLS: A New Approach to Solving Binary Linear Equations
Mod2VQLS is a new quantum hybrid algorithm for solving systems of linear equations modulo 2. In such problems, the goal is to find an n-vector x such that Ax=b, where A is an m*n matrix and b is an m-vector, with all values being 0 or 1 and arithmetic performed modulo 2. Binary linear equations are less common than those with real coefficients, but they still have key mathematical applications and commercial uses. For instance, solving binary linear equations is a crucial step in state-of-the-art sieving approaches to integer factorization.
The Design and Functionality of Mod2VQLS
The design of Mod2VQLS involves defining a quantum circuit implementing matrix-vector products over the relevant finite vector spaces. The circuit has one gate for each nonzero entry in the coefficient matrix. A variational cost function is then derived that can be optimized to produce solutions to the given system. This frames the problem as one of optimizing a variational quantum circuit, a standard approach in quantum machine learning on NISQ (noisy intermediate-scale quantum) hardware.
The Performance of Mod2VQLS
Initial numerical experiments in low dimensions indicate that Mod2VQLS, using the custom rotations ansatz, is on par with the block Wiedemann algorithm, which is the best-known to date solution for this problem. The Mod2VQLS approach uses a number of matrix-vector product calculations, which scales linearly in the system dimension. It is also comparable to the state-of-the-art block Wiedemann method, which also leverages sparsity in the coefficient matrix.
Quantum Circuits and Gates Used in Mod2VQLS
The quantum gates used in the circuits of Mod2VQLS include the single-qubit Pauli X-gate and fractional Y-rotation gate RY(θ), and the 2-qubit CNOT and controlled Z-gates. The Pauli X-gate is used to flip a qubit between the 0 and 1 gates, while the Hadamard H gate is used to put a qubit into a superposition state. The CNOT gate is a 2-qubit entangling gate, and the RY(θ) rotates a single qubit through an angle θ around the Y-axis on the Bloch sphere. The controlled Z-gate is similar to the CNOT gate and entangles two qubits.
Potential Applications of Mod2VQLS
The Mod2VQLS method has potential applications in various fields. It can be used to solve systems of simultaneous linear equations, a standard problem in many areas. It can also be used in situations where the coefficients in the equations are real or complex numbers. When the coefficient matrix is not square, direct methods leveraging the LU or QR decompositions emerge as the natural choice. The Mod2VQLS approach can also be used in recent record-breaking RSA factorization calculations.
In the article titled “Mod2VQLS: A Variational Quantum Algorithm for Solving Systems of Linear Equations Modulo 2”, authors Willie Aboumrad and Dominic Widdows present a new approach to solving systems of linear equations. The article was published in the Applied Sciences journal on January 17, 2024. The full article can be accessed through its DOI: https://doi.org/10.3390/app14020792.
