Quantum Systems Now Calculate Matrix Values with Fewer Measurements

A new variational algorithm for determining eigenvalues and generalised eigenvalues of complex matrices has been developed by Alexander I. Zenchuk and Junde Wu at Federal Research Centre of Problems of Chemical Physics and Medicinal Chemistry RAS, in collaboration with Zhejiang University. The method encodes matrix elements into a quantum system’s pure state, formulating a loss function expressed through probability amplitudes. Key to the algorithm is the use of ancilla state measurement to simplify the superposition, enabling probabilistic loss function construction and derivative calculation for gradient optimisation. With a circuit depth and size of O(N² log N) and O (log N) respectively, the algorithm offers a potentially scalable approach to eigenvalue calculations utilising quantum computation

Reduced circuit complexity enables scalable generalised eigenvalue determination

A significant improvement over previous methods has reduced the circuit depth for this variational quantum algorithm to O(N² log N). This reduction in computational complexity is crucial, as it enables scalable eigenvalue calculations, overcoming limitations previously imposed by the exponential growth of circuit resources with matrix size. Traditional methods for eigenvalue decomposition, such as the QR algorithm, while effective for classical computers, become computationally intractable for large matrices. Quantum algorithms, therefore, offer a potential pathway to address this challenge. The approach encodes complex matrix elements into a quantum system’s pure state, a technique that avoids the non-unitarity issues that have plagued other variational algorithms. Non-unitary operations, while potentially useful, often require careful treatment to maintain the probabilistic interpretation of the quantum state. Numerical simulations on 4 × 4 matrices validated the algorithm, demonstrating its feasibility and accuracy in determining both eigenvalues and generalised eigenvalues. These initial simulations serve as a proof-of-concept, establishing the algorithm’s potential before scaling to larger, more complex matrices.

To construct a loss function and its derivatives, the method utilizes ancilla state measurement, streamlining the gradient optimisation process. The ancilla state, a supplementary quantum system, is measured to project out unwanted terms in the superposition, effectively simplifying the calculation of the loss function. This measurement process introduces a probabilistic element, but allows for efficient estimation of the loss function and its gradients. Alexander I. Zenchuk and Junde Wu evaluated the algorithm’s effectiveness using randomly generated 4 × 4 matrices, assessing 100 pairs under conditions ensuring minimal eigenvalues exceeded 0.1. This constraint on the minimum eigenvalue was implemented to avoid potential numerical instabilities during the optimisation process. Optimisation began with parameters set to 0.5, dynamically increasing to 1.0005 if the loss function decreased by less than 0.001, and conversely increasing by 1.0005 if the loss function itself increased. This adaptive parameter adjustment strategy is designed to accelerate convergence and improve the robustness of the optimisation. The number of iterations required for convergence, denoted N (it), could be approximated by a linear function relating it to the logarithm of the target accuracy, ε, with a coefficient κ(N) of 2936.66 for generalised eigenvalue problems and 1094.51 for standard eigenvalue problems. This logarithmic relationship suggests that achieving higher accuracy requires a proportionally smaller increase in the number of iterations, indicating a relatively efficient convergence behaviour.

For any N×N complex matrix, the algorithm constructs eigenvalues and generalised eigenvalues via a variational method. Variational quantum algorithms rely on minimising an energy function (the loss function in this case) with respect to a set of adjustable parameters. Matrix elements are encoded into a quantum system’s state, and the loss function is expressed with optimisation parameters as probability amplitudes. This encoding allows the eigenvalue problem to be mapped onto a quantum mechanical problem, leveraging the principles of quantum superposition and entanglement. The method measures an ancilla state as the principal step, constructing the loss function and its derivatives to refine optimisation parameters. The circuit depth and size are, respectively, O(N² log N) and O (log N). The logarithmic scaling of the circuit size with respect to the matrix dimension is particularly noteworthy, as it suggests that the algorithm’s resource requirements grow relatively slowly with increasing problem size.

Current scaling limitations hinder application to large matrices

Despite offering a potential speedup for eigenvalue calculations, the new variational algorithm depends on successfully removing unwanted terms via ancilla state measurement. However, the efficiency of this process currently scales unfavourably, limited by a factor of N^-4. This means that the probability of successfully removing the unwanted terms decreases rapidly as the matrix size increases, posing a significant hurdle to scaling the algorithm to tackle genuinely large matrices encountered in fields such as materials science, financial modelling, or complex data analysis. In materials science, accurate eigenvalue calculations are crucial for determining the electronic structure of materials and predicting their properties. In finance, they are used in portfolio optimisation and risk management. The N^-4 scaling suggests that substantial algorithmic improvements or hardware advancements are needed to overcome this limitation. Nevertheless, the development of this variational algorithm represents a valuable contribution, introducing a method for constructing eigenvalues and generalised eigenvalues for arbitrary matrices, potentially offering advantages over existing methods.

Its circuit depth of O(N² log N) and circuit size of O(log N) are features suitable for near-term quantum devices. Near-term quantum devices, also known as Noisy Intermediate-Scale Quantum (NISQ) devices, are characterised by a limited number of qubits and high error rates. Algorithms with low circuit depth and size are particularly well-suited for these devices, as they minimise the impact of noise and decoherence. Rather than relying on unitary transformations, the method encodes matrix elements into a quantum state, avoiding issues with non-Hermitian matrices and simplifying calculations. Non-Hermitian matrices arise in various physical systems and require specialised treatment in classical eigenvalue solvers. Achieving a circuit depth of O(N² log N) with a circuit size scaling logarithmically reduces resource demands, making the algorithm more amenable to implementation on current and near-future quantum hardware. Further research focusing on mitigating the N^-4 scaling factor in the ancilla measurement process is crucial to unlock the full potential of this algorithm.

The researchers developed a new variational algorithm to calculate eigenvalues and generalised eigenvalues for any complex matrix. This method encodes matrix data into a quantum state, offering a potential advantage over traditional approaches and simplifying calculations for non-Hermitian matrices. The algorithm’s circuit depth scales at O(N 2 log N) and circuit size at O(log N), making it potentially suitable for implementation on near-term quantum devices. The authors note that future work should focus on improving the scaling of the ancilla measurement process to address limitations with larger matrices.