Solving the eigenproblems of Hermitian matrices is a significant problem in many fields. The quantum resonant transition (QRT) algorithm has been proposed and demonstrated to solve this problem using quantum devices. To better realize the capabilities of the QRT with recent quantum devices, we improve this algorithm and develop a new procedure to reduce the time complexity. Compared with the original algorithm, it saves one qubit and reduces the complexity with error ϵ from O(1/ϵ2) to O(1/ϵ). Thanks to these optimizations, we can obtain the energy spectrum and ground state of the effective Hamiltonian of the water molecule more accurately and in only 20 percent of the time in a four-qubit processor compared to previous work. More generally, for non-Hermitian matrices, a singular-value decomposition has essential applications in more areas, such as recommendation systems and principal component analysis. The QRT has also been used to prepare singular vectors corresponding to the largest singular values, demonstrating its potential for applications in quantum machine learning.
Solving the eigenproblems of Hermitian matrices is a significant problem in many fields. The quantum resonant transition (QRT) algorithm has been proposed and demonstrated to solve this problem using quantum devices. To better realize the capabilities of the QRT with recent quantum devices, we improve this algorithm and develop a new procedure to reduce the time complexity. Compared with the original algorithm, it saves one qubit and reduces the complexity with error ϵ from O(1/ϵ2) to O(1/ϵ). Thanks to these optimizations, we can obtain the energy spectrum and ground state of the effective Hamiltonian of the water molecule more accurately and in only 20 percent of the time in a four-qubit processor compared to previous work. More generally, for non-Hermitian matrices, a singular-value decomposition has essential applications in more areas, such as recommendation systems and principal component analysis. The QRT has also been used to prepare singular vectors corresponding to the largest singular values, demonstrating its potential for applications in quantum machine learning.
Quantum computing is a promising candidate for accelerating machine learning tasks. Limited by the control accuracy of current quantum hardware, reducing the consumption of quantum resources is the key to achieving quantum advantage. Here, we propose a quantum resonant dimensionality reduction (QRDR) algorithm based on the quantum resonant transition to reduce the dimension of input data and accelerate the quantum machine learning algorithms. After QRDR, the dimension of input data N can be reduced into the desired scale R , and the effective information of the original data will be preserved correspondingly, which will reduce the computational complexity of subsequent quantum machine learning algorithms or quantum storage. QRDR operates with polylogarithmic time complexity and reduces the error dependency from the order of 1 / ε 3 to the order of 1 / ε , compared to existing algorithms. Meanwhile, by avoiding quantum phase estimation, the consumed qubits in QRDR is independent on error ε . Therefore, compared with existing algorithms, our algorithm has achieved the optimal performance in terms of time complexity and space complexity. We demonstrate the performance of our algorithm combining with two types of quantum classifiers, quantum support vector machines and quantum convolutional neural networks, for classifying underwater detection targets and quantum many-body phase, respectively. The simulation results indicate that reduced data extremely improved the processing efficiency following the application of QRDR. As quantum machine learning continues to advance, our algorithm has the potential to be utilized in a variety of computing fields.
It is difficult to calculate the energy levels and eigenstates of a large physical system on a classical computer because of the exponentially growing size of the Hilbert space. In this work, we experimentally demonstrate a quantum algorithm which could solve this problem via simulated resonant transitions. Using a four-qubit quantum simulator in which two qubits are used as ancillas for control and measurement, we obtain the energy spectrum of a 2-qubit low-energy effective Hamiltonian of the water molecule. The simulated transitions allow the state of the quantum simulator to transform and access large regions of the Hilbert space, including states that have no overlap with the initial state. Furthermore, we make use of this algorithm to efficiently prepare specific eigenstates on the simulator according to the measured eigenenergies.
An n-qubit quantum circuit performs a unitary operation on an exponentially large, 2n-dimensional, Hilbert space, which is a major source of quantum speed-ups. We develop a new “Quantum singular value transformation” algorithm that can directly harness the advantages of exponential dimensionality by applying polynomial transformations to the singular values of a block of a unitary operator. The transformations are realized by quantum circuits with a very simple structure - typically using only a constant number of ancilla qubits - leading to optimal algorithms with appealing constant factors. We show that our framework allows describing many quantum algorithms on a high level, and enables remarkably concise proofs for many prominent quantum algorithms, ranging from optimal Hamiltonian simulation to various quantum machine learning applications. We also devise a new singular vector transformation algorithm, describe how to exponentially improve the complexity of implementing fractional queries to unitaries with a gapped spectrum, and show how to efficiently implement principal component regression. Finally, we also prove a quantum lower bound on spectral transformations.
Abstract. Many problems in linear algebra—such as those arising from non-Hermitian physics, transcorrelated quantum chemistry, and differential equations—can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited for this task because eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum superposition of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generate [Formula: see text] Fourier coefficients with [Formula: see text] gates compared to prior approaches with linear cost.
Many problems in linear algebra-such as those arising from non-Hermitian physics, transcorrelated quantum chemistry and differential equations-can be solved on a quan-tum computer by processing eigenvalues of the non-normal input matrices. However, the existing Quantum Singular Value Transformation (QSVT) framework is ill-suited to this task, as eigenvalues and singular values are different in general. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary polynomial transformations on eigenvalues of block-encoded non-normal operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra. QEVT has query complexity to the block encoding nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the Heisenberg-limited scaling for diagonalizable input matrices. As applications, we develop a linear differential equation solver with strictly linear time query complexity for average-case diagonalizable operators, as well as a ground state preparation algorithm that upgrades previous nearly optimal results for Hermitian Hamiltonians to diagonalizable matrices with real spectra. Underpinning our algorithms is an efficient method to prepare a quantum super-position of Faber polynomials, which generalize the nearly-best uniform approximation properties of Chebyshev polynomials to the complex plane. Of independent interest, we also develop techniques to generatenFourier coefficients with 0 (poly log (n)) gates compared to prior approaches with linear cost.
We develop new algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework that encapsulates most known quantum algorithms and serves as the foundation for new ones. Existing implementations of QSVT rely on block encoding, incurring an intrinsic O(logL) ancilla overhead and circuit depth O(Ldλ) for polynomial transformations of a Hamiltonian H=∑k=1LHk, where d is the polynomial degree and λ=∑k∥Hk∥. We introduce a simple yet powerful approach that utilizes only basic Hamiltonian simulation techniques, namely, Trotter methods, to: (i) eliminate the need for block encoding, (ii) reduce the ancilla overhead to only a single qubit, and (iii) still maintain near-optimal complexity. Our method achieves a circuit depth of O(L(dλcomm)1+o(1)), without requiring any complicated multi-qubit controlled gates. Moreover, λcomm depends on the nested commutators of the terms of H and can be substantially smaller than λ for many physically relevant Hamiltonians, a feature absent in standard QSVT. To achieve these results, we make use of Richardson extrapolation in a novel way, systematically eliminating errors in any interleaved sequence of arbitrary unitaries and Hamiltonian evolution operators, thereby establishing a general framework that encompasses QSVT but is more broadly applicable. As applications, we develop end-to-end quantum algorithms for solving linear systems and estimating ground state properties of Hamiltonians, both achieving near-optimal complexity without relying on oracular access. Overall, our results establish a new framework for quantum algorithms, significantly reducing hardware overhead while maintaining near-optimal performance, with implications for both near-term and fault-tolerant quantum computing.