PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen, Chao Yang

arXiv:2203.10236v4quant-phmath.NAmath.QA

TL;DR

Quantum linear algebra depends on efficient circuits for block encodings, but constructing the required oracles is difficult even for structured sparse matrices. This paper gives explicit circuit constructions and MATLAB implementations for selected cases, including sparse matrices and quantum-walk-related encodings. The constructions are polynomial-size for the reported examples, while scaling and oracle-design issues constrain their broader use.

  • Problem

    Efficient block-encoding circuits require explicit structure and value oracles, which remain difficult to construct even for well-structured sparse matrices.

  • Method

    The paper develops explicit oracle and circuit constructions for selected structured sparse matrices, quantum walks, and direct block encodings of stochastic matrices, with MATLAB implementations.

  • Results

    The reported circuits have polynomial gate complexity for the extended-tree and circulant examples, with O(poly(n)) complexity and logarithmic dependence on sparsity for the circulant case.

  • Takeaways & Limitations

    Explicit structure-aware oracle decompositions provide practical block-encoding circuits for selected sparse matrices and quantum-walk constructions.

  • Takeaways & Limitations

    The scaled sparse construction encodes A/s, while transforming the resulting polynomial can require rapidly growing normalization, reducing success probability as s or the polynomial degree increases.

Abstract

from arXiv · show

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.

1 Introduction

Quantum linear algebra algorithms use block encodings and eigenvalue or singular-value transformations, but their practical efficiency depends on constructing efficient circuits for the block-encoding unitary. This paper gives explicit constructions for selected structured sparse matrices, develops oracle-construction strategies, and implements them in MATLAB.

  • Block encoding embeds a properly scaled matrix A in a larger unitary so matrix–vector multiplication can be implemented through state preparation and measurement.
  • Efficient quantum algorithms require decomposing the block-encoding unitary into simpler unitaries, but suitable structure and value oracles are difficult to construct even for sparse matrices.
  • The paper explicitly constructs circuits for selected well-structured sparse matrices and presents general strategies for their structure and matrix-element oracles.
  • The constructions include scaled s-sparse block encodings and quantum-walk-related encodings, with the paper noting both the usefulness and potential cost of the 1/s scaling.

2 Notations and Conventions

This section establishes the paper’s notation for computational-basis states, qubit ordering, elementary gates, controlled operations, and MATLAB circuit construction. It also specifies how integer bitstrings map onto circuit qubits.

  • An integer j is represented by binary bits ji, with j = jn−1·2^(n−1) + ··· + j1·2 + j0.
  • The notation introduces Hadamard, Pauli, and Pauli-Y rotation matrices as basic single-qubit gates.
  • Circuit diagrams number qubits from top to bottom, while the least significant bit j0 maps to the highest-numbered qubit.
  • Controlled operations apply a target gate according to whether control inputs are |1⟩ or |0⟩, represented by solid or open control circles.
  • QCLAB represents MATLAB circuits as ordered gate objects, enabling construction and verification of quantum circuits such as a two-qubit Bell-state circuit.

3 Block encoding and quantum eigenvalue transformation

Block encoding embeds a properly scaled matrix into a unitary whose selected ancilla block represents the matrix. Quantum eigenvalue transformation then uses such an encoding to implement bounded polynomial transformations, while practical construction requires efficient circuit decompositions.

  • A block encoding represents a properly scaled nonunitary matrix A as a submatrix of a larger unitary UA.
  • Applying the block-encoding unitary to an encoded input and postselecting an ancilla can produce A|x⟩, with success probability ||Ax||^2.
  • The matrix must be properly scaled so its spectral norm satisfies ||A||2 ≤ 1, and the paper assumes no gate-set restrictions when constructing UA.
  • A direct square-root construction is impractical because it requires computing and diagonalizing A†A, which generally lacks an efficient O(poly(n)) quantum implementation.
  • Quantum eigenvalue transformation block-encodes a real polynomial p(A) when p has the required parity and satisfies |p(t)| ≤ 1 on [−1,1].
  • The construction follows quantum signal processing, where degree-d polynomials are represented through d + 1 phase factors; optimization-based methods can find phases for high-degree real polynomials.
  • Finding phase angles for arbitrary normalized polynomials is nontrivial, although the cited optimization approach can robustly handle degrees around 10^4.
  • For general matrices, the same circuit framework becomes a quantum singular value transformation rather than a quantum eigenvalue transformation.

4 Efficient quantum circuits for block encodings of s-sparse matrices

The paper develops systematic circuits for structured s-sparse matrices by separating sparsity-location and matrix-value oracles, then decomposing them into elementary gates. These constructions achieve polynomial gate complexity for selected structured examples while typically encoding A/s.

  • A factored 2 × 2 block encoding uses controlled rotations, Hadamard gates, Pauli-X gates, and projectors to decompose the unitary into simpler factors.
  • The 2 × 2 example uses two ancilla qubits in addition to one system qubit, producing a 2^3-dimensional block-encoding unitary.
  • The general sparse-matrix strategy separates a diffusion operator, a location oracle, and a value oracle, with the resulting unitary block encoding A/s.
  • The construction computes the selected matrix element by applying the diffusion, value, and location operations and taking the corresponding ancilla-and-system inner product.
  • Brute-force controlled-gate constructions can require O(N) gates, so the paper targets poly(n) circuits for structured sparsity patterns and characterized nonzero values.
  • For the 2 × 2 matrix, a structured shift pattern makes the location oracle a CNOT, while controlled rotations place the two distinct numerical values.
  • Controlled rotations can be replaced by uniformly controlled rotations implemented with single-qubit rotations and CNOT gates, using θ1 = φ1 + φ2 and θ2 = φ1 − φ2.
  • Substituting the location and rotation circuits together with Ds = H yields the complete block-encoding circuit for the example.

4.2 Banded circulant matrix

The paper constructs an explicit block-encoding circuit for a banded circulant matrix by combining controlled shifts with rotations that encode its three nonzero matrix elements. The resulting circuit has polynomial gate complexity and can be modified for tridiagonal matrices.

  • Matrix structure: The directed cyclic graph yields a banded circulant matrix with α on the diagonal, γ on the superdiagonal, and β on the subdiagonal.Each column has three nonzero elements, so two ancilla qubits encode their row indices.
  • OC circuit: The OC unitary maps |j⟩ to |mod(j − 1, N)⟩, |j⟩, or |mod(j + 1, N)⟩ according to the encoded nonzero-element index.These mappings are implemented with right- and left-shift permutation operators.
  • OC circuit: Controlled shifts apply the required ±1 mappings for sub- and superdiagonal entries, while the unused encoded case performs no shift.The controls are determined by the ancilla state |ℓ⟩.
  • OA circuit: For circulant matrices, controlled Ry rotations depend only on ℓ because the matrix elements are independent of the column index j.The rotations encode α, β, and γ for the diagonal, subdiagonal, and superdiagonal entries, respectively.
  • Complexity: The complete circuit block encodes A/4, uses O(log s) Hadamard gates, controlled rotations, and shifts, and has overall gate complexity poly(n).Controlled shifts can be decomposed into poly(n) two-qubit gates.

4.3 Extended binary tree

The extended binary-tree construction uses an expanded index label to encode child, parent, and diagonal cases, combining controlled multiplication/division by two with shifts. Its circuit generalizes to N = 2^n vertices with O(poly(n)) gate complexity.

  • Matrix structure: The extended binary tree has N = 2^n vertices, with weighted self-loops and parent-child edges defining its adjacency matrix.Weights α apply to ordinary vertices, γ to the root and leaves, and β to parent-child edges.
  • Index encoding: The construction uses three ancilla qubits for ℓ because ℓ denotes nonzero-element types, including cases absent from individual columns.This expands the label beyond the four nonzero entries that any column may contain.
  • OC circuit: The row-index function maps labels to 2j, 2j + 1, j/2, (j − 1)/2, or j for child, parent, and diagonal cases.Multiplication and division by two are combined with controlled shifts to implement these mappings.
  • Arithmetic subcircuits: M2 implements |j⟩ → |2j⟩ using swaps, while D2 reverses those swaps and discards odd j through an ancilla measurement condition.The ancilla flags overflow for M2 and odd inputs for D2, causing the relevant postselected overlap to vanish.
  • OA circuit: The OA circuit uses four controlled rotations to encode β on edges, α on non-leaf diagonals, γ on leaf diagonals, and a root correction.The angles are θ0 = 2 arccos(β), θ1 = 2 arccos(α/4), θ2 = 2 arccos(γ/4), and θ3 = 2 arccos(γ/4 − β/2) − θ1.
  • Complexity: The construction generalizes to larger extended binary trees with O(poly(n)) gate complexity because the numbers of index cases and distinct matrix-element values remain fixed.Each controlled rotation and arithmetic subcircuit decomposes into O(poly(n)) two-qubit gates.

5 Efficient circuits for the block encoding of a symmetric stochastic matrix and quantum walks

The section develops quantum-walk block encodings for symmetric stochastic matrices, explaining why directly encoding P is preferable to encoding P/s and presenting two circuit strategies. It also connects Chebyshev-transformed block encodings to quantum walks and gives an alternative oracle-and-swap construction.

  • A symmetric stochastic matrix P is doubly stochastic and can model a classical random walk on a graph.
  • Quantum walks arise by block encoding the Chebyshev polynomial Tk(P), where Tk(t) = cos(k arccos(t)).
  • After measuring the ancilla in |0⟩, the quantum walk produces Tk(P)|v⟩ rather than P^k|v⟩.
  • Encoding P/s is insufficient for this application because P/s is not stochastic and polynomial rescaling can reduce successful-measurement probability.The rescaling factor can grow rapidly with sparsity; for s = 4 and k = 2, the factor is 31.
  • A direct P block encoding uses an oracle OP together with a swap operation, exploiting stochasticity to avoid an additional ancilla qubit.The approach may require two full-size registers and can use more qubits than the small-s sparsity construction.
  • Theorem 5.1 establishes the resulting block-encoding structure when P is a symmetric stochastic Markov chain and OP implements the required mapping.

P SWAP OP (5.7)

The paper constructs a Hermitian block encoding of a symmetric stochastic matrix P using state preparation, controlled shifts, and SWAP operations, then extends it to Chebyshev polynomials and connects it to Szegedy quantum walks.

  • The constructed unitary is a Hermitian block encoding of P using a SWAP operator.The proof establishes unitarity and Hermiticity before evaluating the encoded matrix elements.
  • The circuit for P prepares the square-root amplitudes of the first circulant column and applies controlled shifts to generate other columns.The state-preparation circuit K exploits sparsity to reduce gate complexity to O(n), while controlled shifts map the first column to each translated column.
  • Quantum eigenvalue transformation uses the symmetric block encoding of P to construct a block encoding of the kth-degree Chebyshev polynomial T_k(P).The required phase sequence has φ0 = π/2, φ1 = · · · = φk−1 = π/2, and φk = 0.
  • The block encoding of T_k(P) is equivalent to performing k steps of a Szegedy quantum walk.The equivalence follows from expressing the polynomial transformation through repeated reflector and SWAP operations.
  • Constructing the symmetric block encoding of P is equivalent to constructing an efficient circuit for the corresponding Szegedy quantum walk.The paper relates its construction to an earlier structured-graph quantum-walk circuit method.

6 Concluding remarks

The concluding remarks emphasize explicit circuit construction as the practical bottleneck for sparse-matrix block encodings. The paper presents structured examples, identifies scope limits, and states hardware assumptions that are not valid for current devices.

  • The paper addresses the limited explicit construction of efficient quantum circuits for block encoding unitaries.Earlier work provided general oracle strategies, but explicit circuit realizations had received comparatively little attention.
  • For an s-sparse matrix A, the block encoding circuit combines an O_c block for nonzero structure with an O_A block for numerical values.The paper notes that these oracle constructions can depend on each other when preserving the desired sparsity structure.
  • For arbitrary sparse matrices, constructing an efficient O_c may be difficult, and a separate O_r unitary may be needed to encode row sparsity.This marks a scope boundary for the general construction procedure.
  • The general construction is unsuitable for symmetric stochastic matrices used to implement quantum walks on the same graph.The paper instead uses a symmetric block encoding of P and connects T_k(P) circuits to Szegedy quantum-walk constructions.
  • The circuit model assumes arbitrary single-qubit rotations, multiqubit controls, and unrestricted qubit connectivity.The paper states that these assumptions do not hold on existing devices and are not expected for at least early fault-tolerant computers.

7 Efficient circuits for powers of a shift operator

The paper shows how powers of an n-qubit shift operator can be implemented through controlled lower-dimensional shifts rather than repeated full shift circuits.

  • Powers of an n-qubit L-shift operator can be implemented efficiently without repeating the entire shift circuit.The construction decomposes the power using the binary representation of the shift amount.
  • The construction includes dedicated circuits for L^2 and related powers such as R^2.These decompositions provide concrete circuit components for implementing shift powers.
  • The resulting circuit applies controlled L^k operations successively for k = n, n−1, ..., 1.The controls are the corresponding binary digits of j, as illustrated by the n = 3 circuit.

8 Hermitian block encoding of Hermitian sparse matrices

The paper gives a general Hermitian block encoding for real symmetric or complex Hermitian sparse matrices, using controlled structure and value oracles together with diffusion and SWAP operations.

  • A general block encoding of a Hermitian matrix need not itself be Hermitian, motivating a separate Hermitian construction.The paper notes that Hermitian block encodings can simplify theoretical treatments such as quantum walks.
  • The controlled structure oracle O_C maps a column index and nonzero-element label to the corresponding row index.Its action is O_C|ℓ⟩|j⟩ = |c(j, ℓ)⟩|j⟩.
  • The value oracle encodes each matrix entry A_ij = |A_ij|e^{iθ_ij} using the uniquely defined square root |A_ij|e^{iθ_ij/2}.This square-root encoding supplies the amplitudes and phases needed by the Hermitian block-encoding circuit.
  • The circuit combines the value and structure oracles with a diffusion operator and a SWAP between the last two n-qubit registers.The resulting unitary is stated to be a Hermitian block encoding of A.
  • The construction is verified by showing that the all-zero ancilla matrix element equals A_ij/s.The proof applies the diffusion, value, and structure operations before analyzing the SWAP action.

9 Additional results on quantum walks

This section reviews Markov-chain properties and constructs the Szegedy quantum-walk ingredients from a reversible transition matrix. Reversibility permits analysis through a symmetric discriminant matrix with the same eigenvalues as the original matrix.

  • Markov-chain properties: A stochastic matrix P describes transition probabilities for a random walk, with stationary-state and ergodicity properties characterizing long-run behavior.An ergodic chain is irreducible and aperiodic and has a unique stationary state.
  • Discriminant matrix: The stationary-state vector |π⟩ is a normalized eigenvector of D with eigenvalue 1.Because π_i > 0, the stationary distribution can be used in the corresponding quantum-walk construction.
  • Discriminant matrix: For reversible P, the discriminant matrix D is symmetric and shares P’s eigenvalues, allowing spectral analysis of nonsymmetric P through D.The transformation is D = diag(√π)P diag(√π)−1.
  • Szegedy quantum walk: Szegedy’s quantum walk is constructed from oracle-defined quantum states, projection operators, and reflections whose product forms the walk operator.The construction uses two reflection operators derived from the projections.

P SWAP . (9.10)

The section explains why quantum walks can outperform classical random walks for spectral-gap-dependent tasks and illustrates this with marked-vertex detection. The example contrasts a uniform stationary outcome without a marked vertex with rapid concentration or measurement-probability change when one is present.

  • Quantum-walk transformation: k steps of Szegedy’s quantum walk correspond to a block encoding of T_2k(D), linking quantum-walk evolution to Chebyshev-transformed discriminant matrices.This follows from the relation between the walk operator and qubitization.
  • Quantum-walk efficiency: For reversible walks, the transformed second-largest eigenvalue can approach that of P^k, explaining the potential asymptotic speedup through the spectral gap.The comparison follows from matching Taylor expansions under the appropriate choice of walk-step count.
  • Marked-vertex detection: Without a marked vertex, the uniform distribution remains unchanged under P, whereas the marked-vertex matrix is nonsymmetric and drives the classical walk toward the marked state.For the marked case, convergence occurs after O(N) random-walk steps.
  • Marked-vertex detection: The quantum procedure applies the block encoding of the discriminant matrix to a prepared state and tests the probability of measuring |0^n⟩.The measurement probability distinguishes the unmarked and marked cases.
  • Marked-vertex detection: 1/N is the marked-case success probability after the optimal number of quantum-walk steps, compared with the initial unmarked-case probability of 1.This enables high-confidence detection in O(√N) steps, a quadratic improvement over the classical O(N) requirement.
  • Numerical demonstration: The n = 6 QCLAB simulation uses circuits for both discriminant matrices and finds that a small number of steps suffices to distinguish the two cases.The states are maximally distinguishable at k_opt.
Loading 2203.10236v4…