Reducing C-NOT Counts for State Preparation and Block Encoding via Diagonal Matrix Migration

• URL: http://arxiv.org/abs/2603.16492v1
• Date: Tue, 17 Mar 2026 13:20:46 GMT
• Title: Reducing C-NOT Counts for State Preparation and Block Encoding via Diagonal Matrix Migration
• Abstract summary: We give algorithms with lower C-NOT counts for both the state preparation and block encoding.<n>For a general $n$-qubit state, we improve the C-NOT count from Plesch-Brukner algorithm.<n>For block encoding, our single-ancilla protocol for $2n-1times 2n-1$ matrices uses the spectral norm as subnormalization.
• Score: 10.184239233596562
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum state preparation and block encoding are versatile and practical input models for quantum algorithms in scientific computing. The circuit complexity of state preparation and block encoding frequently dominates the end-to-end gate complexity of quantum algorithms. We give algorithms with lower C-NOT counts for both the state preparation and block encoding. For a general $n$-qubit state, we improve the C-NOT count from Plesch-Brukner algorithm, proposed in 2011, from $(23/24)2^n$ to $(11/12)2^n$. For block encoding, our single-ancilla protocol for $2^{n-1}\times 2^{n-1}$ matrices uses the spectral norm as subnormalization and achieves a C-NOT count leading term $(11/48)4^n$. This result even exceeds the lower bound of $(1/4)4^n$ for $n$-qubit unitary synthesis. Further optimization is performed for low-rank matrices, which frequently arise in practical applications. Specifically, we achieve the C-NOT count leading term $(K+(11/12))2^n$ for a rank-$K$ matrix. Our approach builds upon the recursive block-ZXZ decomposition from Krol et al. and introduces a diagonal matrix migration technique based on the commutativity of the diagonal matrix and the uniformly controlled rotation about the $z$-axis to minimize the use of C-NOT gates.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Lowering LCU Circuit Width through Maximum-Weight Birkhoff-von Neumann Decomposition [0.0]
  We show that a bottleneck variant of Birkhoff's algorithm reduces the number of permutations to $O(Nlog(varepsilon))$.<n>The quadratic reduction in term count directly shrinks the ancilla register from $2log N$ to $log N$ qubits.<n>This structure can be exploited to achieve high success probability without amplitude amplification.
  arXiv  Detail & Related papers  (2026-05-22T04:29:13Z)
• Quantum block encoding for semiseparable matrices [0.0]
  We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors.<n>To encode the matrix, the algorithm needs $2log(N)+7$ ancillary qubits. This process takes polylogarithmic time and has an error of $mathcalO(N2)$, where $N$ is the matrix size.
  arXiv  Detail & Related papers  (2026-03-19T16:49:13Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Two Quantum Algorithms for Nonlinear Reaction-Diffusion Equation using Chebyshev Approximation Method [1.775629639045375]
  We present two new quantum algorithms for reaction-diffusion equations that employ the truncated Chebyshevpoly approximation.<n>We derive the sufficient conditions for the diagonalization of the Carleman embedding matrix.<n>The success of the diagonalization is based on a conjecture that a specific trigonometric equation has no integral solution.
  arXiv  Detail & Related papers  (2025-10-21T19:14:23Z)
• Arbitrary state creation via controlled measurement [49.494595696663524]
  This algorithm creates an arbitrary $n$-qubit pure quantum superposition state with precision of $m$-decimals.<n>The algorithm uses one-qubit rotations, Hadamard transformations and C-NOT operations with multi-qubit controls.
  arXiv  Detail & Related papers  (2025-04-13T07:23:50Z)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  We propose the variational quantum singular value decomposition based on encoding the elements of the considered $Ntimes N$ matrix into the state of a quantum system of appropriate dimension.<n> Controlled measurement is involved to avoid small success in ancilla measurement.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Preconditioned Block Encodings for Quantum Linear Systems [0.0]
  Matrix preconditioning is a well-established classical technique to reduce $kappa$ by multiplying $A$ by a preconditioner $P$.<n>We consider four preconditioners and two encoding approaches for block encodings.<n>Their impact on subnormalisation factors and condition number $kappa$ are analysed using practical matrices from Computational Fluid Dynamics.
  arXiv  Detail & Related papers  (2025-02-28T10:08:14Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• S-FABLE and LS-FABLE: Fast approximate block-encoding algorithms for unstructured sparse matrices [0.0]
  The Fast Approximate BLock-Lazy algorithm (FABLE) is a technique to block-encode arbitrary $Ntimes N$ dense matrices into quantum circuits. We describe two modifications of FABLE to efficiently encode sparse matrices.
  arXiv  Detail & Related papers  (2024-01-08T20:57:16Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.