Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

DOI10.1137/22M1484298MaRDI QIDQ6130653zbMATH OpenFDO

Authors Daan Camps, Lin Lin, R. Van Beeumen, Chao Yang

Publication date 3 April 2024

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.10236

zbMATH Keywords

block encodingquantum circuitquantum eigenvalue transformationquantum linear algebraquantum singular value transformationquantum walk

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

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.

Cites work

• Efficient quantum circuits for Szegedy quantum walks
• On the relationship between continuous- and discrete-time quantum walk
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum computing. A gentle introduction
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum walks in higher dimensions

Cited in

(7)

• Quantum representation and geometric transformation of 3D images
• Dilation theorem via Schrödingerization, with applications to the quantum simulation of differential equations
• Time-dependent Hamiltonian simulation via Magnus expansion: algorithm and superconvergence
• Efficient quantum Gibbs samplers with Kubo-Martin-Schwinger detailed balance condition
• Quantum time-marching algorithms for solving linear transport problems including boundary conditions
• Quantum simulation-based optimization for cooling system design
• An implementation of quantum oracles for the finite element method

This page was built for publication: Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6130653)