Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:DTVMTINWrecord.jsonopen to challenge →
read the original abstract
Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest A in a larger unitary transformation U that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of A, which is difficult in general, and not trivial even for well-structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well-structured sparse matrices, and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
This paper has not been read by Pith yet.
Forward citations
Cited by 10 Pith papers
-
Explicit Quantum Circuit Simulation of Nonlinear 1-Dimensional Fluid with Carleman-linearized Boltzmann Method
Explicit quantum-circuit simulation of nonlinear 1D fluid via second-order Carleman-linearized Boltzmann equation and QSVD Taylor ODE solver, with logarithmic scaling analysis.
-
Explicit Block Encodings of Discrete Laplacians with Mixed Boundary Conditions
A modular block-encoding framework for finite-difference Laplacians supporting arbitrary combinations of Dirichlet, periodic, and Neumann boundary conditions across dimensions.
-
Phase Estimation with Compressed Controlled Time Evolution
A compression protocol for controlled time evolution of local translationally invariant Hamiltonians achieves O(t polylog(t N/ε)) circuit depth with additive control overhead, demonstrated via 414 CNOT gates for itera...
-
Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation
Quantum algorithm approximates k-th spectral gap Δ_k and midpoint μ_k of Hermitian matrix to εΔ_k error with O(N²/(ε² Δ_k²) polylog) QRAM complexity, claiming speedup for large gaps, plus Ω(N²) black-box lower bound.
-
Quantum Channel Polynomial Processing
QCPP implements polynomial transformations of Hamiltonians via stochastic mixtures of unitary channels, achieving a tunable tradeoff between query and sample complexity.
-
Fixing Divergence in Carleman Linearization via Analytical Continuation
A Möbius conformal map and regularized incomplete beta function fix the long-time divergence of Carleman linearization for logistic, KPP-Fisher, and phase-field equations.
-
Quantum algorithm for solving differential equations using SLAC derivatives
Presents LCU block-encodings for SLAC derivative operators, applies Shannon wavelets and preconditioning, and obtains O(d n^3 α^(k) log(1/ε)) gate complexity for d-dimensional PDEs via QLSA.
-
Analog photonic simulator for large-scale transport
Continuous-variable photonic platform with 20,000-mode cluster state simulates advection transport equation, achieving relative errors of 0.8% and 0.92% on first- and second-order moments via homodyne readout.
-
Quantum algorithm for solving differential equations using SLAC derivatives
Efficient quantum block-encodings of SLAC first-order derivative and Laplacian operators are built with LCU, state preparation, wavelet multi-scale transforms, and preconditioning to solve PDEs via QLSA with analyzed ...
-
Efficient Multi-Controlled Gate Implementation in Trapped-Ion Systems
Exploiting sign freedom in Cirac-Zoller red-sideband pulses enables pulse cancellation that cuts multi-controlled gate times and reduces LCU select-operator pulse cost from O(L log L) to O(L).
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.