Quantum Computers Now Handle a Wider Range of Complex Calculations

Researchers at University of the Basque Country UPV, led by Xabier Gutiérrez, have developed a novel technique extending the capabilities of Quantum Signal Processing (QSP) and Quantum Singular Value Transformation (QSVT) to encompass arbitrary, non-Hermitian matrices that lack diagonalizability. Current limitations of QSP and QSVT restrict their application to unitary or Hermitian matrices, hindering their broader utility in quantum algorithm design. This new method offers a more systematic approach by enabling polynomial transformations of matrix eigenvalues, thereby significantly expanding the range of problems addressable through quantum computation.

Logarithmic scaling of ancillary qubits enables quantum computation on general matrices

A significant bottleneck in scaling quantum algorithms involving block-encoded matrices has been the number of ancillary qubits required for transformations. Previous methods demanded additional qubits proportional to the matrix size, severely restricting scalability for large matrices. The team has achieved a substantial improvement by reducing the number of ancillary qubits needed to transform block encodings to n-regular ones to O (log n). This logarithmic scaling represents a crucial advancement, as it allows the application of QSP and QSVT to arbitrary square matrices, including those that are non-Hermitian and non-diagonalizable. The implications are far-reaching, as these previously inaccessible matrices frequently arise in complex physical and computational models.

The construction of these n-regular block encodings, requiring only O(log n) additional qubits, is a key step towards the broader application of quantum algorithms. This achievement extends QSP and QSVT beyond their traditional limitations, allowing for the manipulation of a wider class of matrices. Specifically, the construction utilises a quantum incrementer, a circuit designed to repeatedly add a value of one to a quantum register. This incrementer is crucial for ‘dumping branches’, effectively discarding unwanted quantum states, after repeated applications of the block encoding. Maintaining a clean signal is paramount for ensuring accurate eigenvalue transformations, particularly when dealing with matrices in Jordan normal form, which are notoriously difficult to diagonalise. While achieving (n+1)-regular encodings remains a challenge, and thus limits the degree of polynomial transformations achievable in practice, the current O(log n) scaling provides a substantial leap forward. The Jordan normal form is particularly relevant as it represents the most general form of a matrix, encompassing all possibilities including diagonalisable and Hermitian matrices as special cases. This means the technique is not merely extending existing capabilities, but fundamentally broadening the scope of quantum computation.

The concept of block encoding itself is central to this advancement. It involves representing a matrix as a quantum operator acting on a set of qubits, allowing for efficient manipulation within a quantum circuit. The ‘regularity’ of the block encoding refers to the structure of this representation, with higher regularity generally simplifying the implementation of quantum algorithms. Achieving n-regularity allows for more efficient application of polynomial transformations, as the matrix can be effectively ‘raised to a power’ within the quantum circuit. The logarithmic scaling of ancillary qubits for achieving n-regularity is what makes this approach practical for larger matrices, overcoming the limitations of previous methods.

Expanding quantum computation to encompass non-Hermitian matrix problems

The ongoing refinement of quantum computational methods is enabling the tackling of increasingly complex problems across diverse scientific disciplines. While Quantum Signal Processing and Quantum Singular Value Transformation have proven highly effective at manipulating specific matrix types, their inherent limitations with arbitrary, non-Hermitian matrices presented a significant obstacle. These techniques traditionally struggle when confronted with matrices lacking easily defined properties, such as positive definiteness or diagonalisability. This work introduces ‘n-regular block encoding’ as a technique for representing matrices that allows for polynomial transformations of their eigenvalues, thereby broadening the scope of solvable problems and opening up new avenues for quantum algorithm development.

Many real-world problems, particularly those arising in areas like materials’ science, financial modelling, and control theory do not neatly fit into the categories of Hermitian or diagonalizable matrices. These problems often involve complex interactions and non-equilibrium dynamics best represented by more general, non-Hermitian forms. For example, modelling the time evolution of an open quantum system naturally leads to non-Hermitian effective Hamiltonians. This new ‘n-regular block encoding’ offers a pathway to address these previously intractable scenarios through precise eigenvalue manipulation, opening doors to a wider range of quantum algorithms and potentially accelerating solutions in these critical fields. The ability to perform polynomial transformations of eigenvalues is particularly powerful, as it allows for the implementation of functions of the matrix, such as the inverse or the square root, which are essential for many quantum algorithms.

A framework for polynomial transformations of matrix eigenvalues expands the potential of quantum computation beyond the limitations previously imposed on non-Hermitian matrices. A method utilising ‘n-regular block encoding’, a carefully constructed representation of a matrix within a quantum computer, has been created to achieve this. This allows repeated applications of the block encoding to yield higher powers of the original matrix, effectively circumventing the restrictions affecting Quantum Signal Processing and Quantum Singular Value Transformation. The implications extend beyond simply solving previously unsolvable problems; it also allows for the development of more efficient quantum algorithms for existing problems by leveraging the full power of matrix manipulation. Further research will focus on optimising the quantum incrementer and exploring methods for achieving (n+1)-regular encodings to further enhance the capabilities of this promising technique.

The researchers developed a new method for manipulating the eigenvalues of square matrices using ‘n-regular block encoding’ within a quantum computer. This overcomes limitations in existing quantum techniques, such as Quantum Signal Processing and Quantum Singular Value Transformation, which previously struggled with matrices that are not Hermitian or easily diagonalised. By enabling polynomial transformations of eigenvalues, this work expands the range of problems addressable by quantum algorithms, particularly those found in fields like materials science and financial modelling. The authors intend to optimise the quantum incrementer and explore further enhancements to the encoding method in future work.