Methods for Reducing Ancilla-Overhead in Block Encodings

Francisca Vasconcelos, András Gilyén · 2025

Read Methods for Reducing Ancilla-Overhead in Block Encodings by Francisca Vasconcelos, András Gilyén (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-07900.txt.

Introduction

Francisca Vasconcelos and András Gilyén cut the helper-qubit cost of block encodings, a core building block of quantum algorithms, in a paper published in two thousand twenty-five. A block encoding embeds a matrix inside a larger unitary, and many algorithms use them, but the extra ancilla qubits they demand can be heavy.

The paper attacks the overhead two ways. First, it proves a space-time trade-off: any block encoding can be reworked to uncompute all but one ancilla, freeing the rest for later use at some cost in time. Second, it studies how many ancillae coherent multiplication of block encodings truly needs. Exact multiplication provably requires a logarithmic number, which is optimal. But approximate multiplication, in certain regimes, reaches high precision with a single ancilla. That is a space-accuracy trade-off. The results help algorithm designers budget scarce qubits.

Catalog record

CREATORFrancisca Vasconcelos, András Gilyén
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE107 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-07900

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Methods for Reducing Ancilla-Overhead in Block Encodings Francisca Vasconcelos, András Gilyén Abstract Block encodings are a fundamental primitive in quantum algorithms but often require large ancilla overhead. In this work, we introduce novel techniques for reducing this overhead in two distinct ways. In Part I, we devise a method for any block encoding that approximately uncomputes all but one of the ancillae (freeing up the ancillae for reuse in later parts of a quantum algorithm), thereby effectively providing a “space-time tradeoff”. More precisely, for any matrix A A , such that ‖ A ‖ ≤ 1 − δ \|A\|\leq 1-\delta , our protocol coherently computes an ε \varepsilon -approximate single-ancilla block-encoding of A A , constructed through O ⁡ ( 1 δ ​ log ⁡ ( 1 ε ) ) O(\frac{1}{\delta}\log(\frac{1}{\epsilon})) queries to any block encoding U U and U † U^{\dagger} . We establish a connection between this procedure and the problem of “phase correction” in modular quantum signal processing. In Part II, we evaluate the minimum number of ancillae required to perform coherent multiplication of block encodings. First, we prove that ⌈ log 2 ​ K ⌉ \lceil\log_{2}K\rceil ancillae is optimal for exact multiplication of block encodings. This lower-bound is saturated by a slight modification to the “compression gadget” of Low and Wiebe (2019). Furthermore, we study ε \varepsilon - approximate multiplication of block encodings in regimes where the block encodings have 𝒪 ⁡ ( 1 / K ) \mathcal{O}(1/K) -bounded deviation from the identity and propose the p p -Modular Addition Compression Gadget which is shown to achieve accuracy 𝒪 ⁡ ( K − 2 p ) \mathcal{O}(K^{-2^{p}}) using just p p additional ancillae. We discuss applications of the p p -MACG to Hamiltonian simulation and quantum differential equation solvers. Finally, we demonstrate how oblivious amplitude amplification can boost the success probability of an ε \varepsilon -approximate multiplcation of block encodings circuit to Ω ⁡ ( 1 − ε 2 ) \Omega(1-\varepsilon^{2}) . 1 Introduction Although quantum computation is inherently unitary, quantum subsystems can undergo non-unitary dynamics, if one allows post-selection. Thus, non-unitary quantum computation on an n -qubit system can be achieved by expanding the computational workspace, i.e., adding extra “ancillary” qubits, and treating the main n -qubit system as a subsystem of this larger workspace. Interaction with and measurement of the ancillary “bath” can induce non-unitary, irreversible dynamics on the main n -qubit subsystem. While this procedure may sound abstract, decades of quantum algorithms research has formalized a simple, yet fundamental primitive for implementing such non-unitary embeddings in quantum computation — originally defined by [ LC19 ] and subsequently termed by [ CGJ18 ] as a “block encoding”. Formally, a block encoding embeds a normalized, arbitrary (i.e., non-unitary) matrix A into a larger unitary matrix, \displaystyle U_{A}=\begin{bmatrix}A&*\\ *&*\end{bmatrix},\quad\text{ where }A=(\bra{0^a}\otimes I)~U_{A}~(\ket{0^a}\otimes I). (1) More generally, the unitary \widetilde{U}_{A} is called an (\alpha,a,\varepsilon) -block encoding of A if \displaystyle\|A-\alpha\cdot\bra{0^a}\widetilde{U}_{A}\ket{0^a}\|\leq\varepsilon. (2) Given an arbitrary n -qubit state \ket{\psi} , A\ket{\psi} is implemented via the circuit that computes U_{A}\ket{0^a}\ket{\psi} , performs a measurment on a the first a ancilla qubits, and post-selects on the 0^{a} outcome. Despite its simplicity, block encoding has become one of the most important primitives in quantum algorithms [ DMB+23 ] , largely thanks to qubitization [ LC19 ] and quantum singular value transformation [ GSLW19 ] , and their applications, e.g., in Hamiltonian simulation [ BCC+15 , LW19 ] and scientific computing. Indeed, block encoding methods have led to improved linear systems solvers [ CGJ18 ] (with applications to regression), differential equation solvers [ FLT23 ] , quantum information protocols [ GLM+20 ] , optimization [ vAG19 ] , statistical estimation [ GL20 ] , Gibbs sampling [ CKBG23 ] , state preparation [ LT20 ] , and tomography [ vACGN23 ] algorithms. In practice, however, implementation of block encodings can be resource intensive, requiring substantial computation time and ancilla space overhead [ CDS+22 ] . Several techniques have also been established for manipulation of block encodings. For example, the linear combination of unitaries procedure [ CW12 ] block encodes convex combinations (i.e., addition) of general matrices. In this work, we specifically focus on procedures for multiplication of a large number of block-encoded matrices. Beyond being an important subroutine for data embedding and processing, multiplication of block encodings plays an important role in quantum simulation algorithms [ BCC+15 , LW19 ] and quantum differential equation solvers [ FLT23 ] . Although multiplication of block encodings can be implemented with mid-circuit measurements (i.e. incoherent computation), such implementations are often challenging and limited in practice. For example, in superconducting architectures measurement times ( \sim 100 ns- 1\mu s) are typically much longer than gate times ( \sim 10 - 100 ns) [ KKY+19 ] , meaning repeated measurement could severely slow down the overall computation time. In neutral atom systems, imaging ejects atoms from the trap, which are time-consuming to reload [ BEG+24 , MNB+24 ] . Therefore, it is natural to consider coherent implementations of multiplication of block encodings, via deferred measurement. Furthermore, coherent implementations have the important added benefits that they can be used as black-box subroutines in quantum algorithms and that amplitude amplification can be used to boost the probability of the successful measurement sequence to \Omega(1) . As discussed, practical implementation and manipulation of block-encodings can be resource intensive. This work focuses on reducing the number of ancillae necessary for block encoding operations, via two distinct approaches: • In Part I ( Section 2 and Appendix A ) we assume black-box access to a block encoding U_{A} implemented with many ancillae. We give a protocol for coherently uncomputing all but one of a U_{A} ’s ancillae (freeing them for reuse later in an algorithm), effectively establishing a “space-time tradeoff”. We show that for any matrix A (s.t. \|A\|<0.99 ) and error \varepsilon , one can get an \varepsilon -precise single-ancilla block encoding of A with \mathcal{O}(\log(1/\epsilon)) uses of U_{A}^{\pm 1} . We conclude by establishing a connection between our procedure and the problem of “phase correction” in modular quantum signal processing. • In Part II ( Section 3 and Appendix B ), we focus specifically on the ancilla overhead of multiplication of block encodings. We prove that exact multiplication of K block encodings requires at least \lceil\log_{2}K\rceil ancillae — a lower-bound saturated by a slight modification to the compression gadet of [ LW19 ] . Moreover, we propose a method for approximate multiplication of block encodings and show that, for multiplication of block encodings with bounded distance from the identity, approximate multiplication can be achieved with \mathcal{O}(1) ancillae, surpassing the exact multiplication ancilla lower-bound. We describe how the guarantees of this procedure are relevant in the settings of Hamiltonian simulation and quantum differential equation solvers. Finally, we show that oblivious amplitude amplification can be used to boost the success probability for \varepsilon -approximate multiplication of block encodings to \Omega(1-\varepsilon^{2}) . 2 Part I: Approximate Single-Ancilla Block Encodings As discussed in the introduction, implementation of block encodings can often be resource intensive, especially with respect to ancilla overhead. Given an “inefficient” block encoding (i.e. a block encoding requiring more than one ancilla qubit) of matrix \mathcal{A} , with \|\mathcal{A}\|<1 , we prove

Read the complete text