Randomized Quantum Singular Value Transformation

• URL: http://arxiv.org/abs/2510.06851v1
• Date: Wed, 08 Oct 2025 10:14:15 GMT
• Title: Randomized Quantum Singular Value Transformation
• Abstract summary: We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT)<n>Standard implementations of QSVT rely on block encodings of the Hamiltonian, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms.<n>Our algorithms use only a single ancilla qubit and entirely avoid block encodings.
• Score: 18.660349597156266
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the first randomized algorithms for Quantum Singular Value Transformation (QSVT), a unifying framework for many quantum algorithms. Standard implementations of QSVT rely on block encodings of the Hamiltonian, which are costly to construct, requiring a logarithmic number of ancilla qubits, intricate multi-qubit control, and circuit depth scaling linearly with the number of Hamiltonian terms. In contrast, our algorithms use only a single ancilla qubit and entirely avoid block encodings. We develop two methods: (i) a direct randomization of QSVT, where block encodings are replaced by importance sampling, and (ii) an approach that integrates qDRIFT into the generalized quantum signal processing framework, with the dependence on precision exponentially improved through classical extrapolation. Both algorithms achieve gate complexity independent of the number of Hamiltonian terms, a hallmark of randomized methods, while incurring only quadratic dependence on the degree of the target polynomial. We identify natural parameter regimes where our methods outperform even standard QSVT, making them promising for early fault-tolerant quantum devices. We also establish a fundamental lower bound showing that the quadratic dependence on the polynomial degree is optimal within this framework. We apply our framework to two fundamental tasks: solving quantum linear systems and estimating ground-state properties of Hamiltonians, obtaining polynomial advantages over prior randomized algorithms. Finally, we benchmark our ground-state property estimation algorithm on electronic structure Hamiltonians and the transverse-field Ising model with long-range interactions. In both cases, our approach outperforms prior work by several orders of magnitude in circuit depth, establishing randomized QSVT as a practical and resource-efficient alternative for early fault-tolerant quantum devices.

Related papers

• An analysis of iterative refinement for quantum linear system solvers [0.06157382820537719]
  We present an iterative refinement (IR) framework for improving the precision dependence of algorithms that combine a quantum linear system algorithm (QLSA) with quantum state tomography.<n>We evaluate the proposed scheme through numerical experiments on both quantum simulators and real quantum hardware.
  arXiv  Detail & Related papers  (2026-09-09T14:38:28Z)
• Are Randomized Quantum Linear Systems Solvers Practical? [0.0]
  randomized quantum algorithms have been proposed in the context of quantum simulation and quantum linear algebra.<n>We provide explicit bounds on all relevant parameters that control the total error for a randomized quantum linear systems solver.<n>Our work serves as a bridge between theoretical algorithmic proposals and efficient hardware implementations.
  arXiv  Detail & Related papers  (2025-10-15T17:12:55Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• RhoDARTS: Differentiable Quantum Architecture Search with Density Matrix Simulations [44.13836547616739]
  Variational Quantum Algorithms (VQAs) are a promising approach to leverage Noisy Intermediate-Scale Quantum (NISQ) computers.<n> choosing optimal quantum circuits that efficiently solve a given VQA problem is a non-trivial task.<n>Quantum Architecture Search (QAS) algorithms enable automatic generation of quantum circuits tailored to the provided problem.
  arXiv  Detail & Related papers  (2025-06-04T08:30:35Z)
• Quantum Discrete Adiabatic Linear Solver based on Block Encoding and Eigenvalue Separator [5.138262101775231]
  The rise of quantum computing has spurred interest in quantum linear system problems.<n>The performance of the HHL algorithm is constrained by its dependence on the square of the condition number.<n>This work proposes a quantum discrete adiabatic linear solver based on block encoding and eigenvalue separation techniques.
  arXiv  Detail & Related papers  (2024-12-09T04:50:48Z)
• Block encoding bosons by signal processing [0.0]
  We demonstrate that QSP-based techniques, such as Quantum Singular Value Transformation (QSVT) and Quantum Eigenvalue Transformation for Unitary Matrices (QETU) can themselves be efficiently utilized for BE implementation.<n>We present several examples of using QSVT and QETU algorithms, along with their combinations, to block encode Hamiltonians for lattice bosons.<n>We find that, while using QSVT for BE results in the best gate count scaling with the number of qubits per site, LOVE-LCU outperforms all other methods for operators acting on up to $lesssim11$ qubits.
  arXiv  Detail & Related papers  (2024-08-29T18:00:02Z)
• Benchmarking Variational Quantum Eigensolvers for Entanglement Detection in Many-Body Hamiltonian Ground States [37.69303106863453]
  Variational quantum algorithms (VQAs) have emerged in recent years as a promise to obtain quantum advantage. We use a specific class of VQA named variational quantum eigensolvers (VQEs) to benchmark them at entanglement witnessing and entangled ground state detection. Quantum circuits whose structure is inspired by the Hamiltonian interactions presented better results on cost function estimation than problem-agnostic circuits.
  arXiv  Detail & Related papers  (2024-07-05T12:06:40Z)
• Characterizing randomness in parameterized quantum circuits through expressibility and average entanglement [39.58317527488534]
  Quantum Circuits (PQCs) are still not fully understood outside the scope of their principal application.<n>We analyse the generation of random states in PQCs under restrictions on the qubits connectivities.<n>We place a connection between how steep is the increase on the uniformity of the distribution of the generated states and the generation of entanglement.
  arXiv  Detail & Related papers  (2024-05-03T17:32:55Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Improved iterative quantum algorithm for ground-state preparation [4.921552273745794]
  We propose an improved iterative quantum algorithm to prepare the ground state of a Hamiltonian system. Our approach has advantages including the higher success probability at each iteration, the measurement precision-independent sampling complexity, the lower gate complexity, and only quantum resources are required when the ancillary state is well prepared.
  arXiv  Detail & Related papers  (2022-10-16T05:57:43Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• Ground state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices [3.1952399274829775]
  We develop a tool called quantum eigenvalue transformation of unitary matrices with reals (QET-U) This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model.
  arXiv  Detail & Related papers  (2022-04-12T17:11:40Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.