PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum space-depth tradeoffs for coherent block encodings

Yuxin Zhang, Changpeng Shao

arXiv:2607.01843v2quant-phcs.CC

TL;DR

Standard LCU block encodings are depth-efficient but use logarithmically many ancillas, leaving a quantitative workspace-versus-depth question for approximate coherent constructions. The paper develops low-ancilla constructions and lower bounds in coherent simulation and repeated-query LCU models. It establishes tradeoffs within these models and an optimal approximate-degree dependence for normalized trace estimation in DQC1.

  • Problem

    Standard LCU uses O(log L) ancillas, and how much workspace depth-efficient approximate block encoding requires is a central question.

    Source: §1 · p. 3

  • Method

    The paper combines low-ancilla block-encoding constructions with lower-bound analyses for coherent simulation and repeated-query LCU.

    Source: §1 · p. 3, §1.2 · p. 4, §7 · p. 34

  • Results

    Within the Suzuki-based architecture, constant ancillas cannot yield polylogarithmic dependence on inverse precision, while normalized trace estimation in DQC1 has complexity linear in approximate degree with a matching query lower bound.

    Source: §1.6 · p. 9, §7 · p. 34

  • Takeaways & Limitations

    The results quantify space-depth and space-query tradeoffs in two circuit models, and establish optimal approximate-degree dependence for the stated DQC1 setting.

    Source: §1.6 · p. 9, §7 · p. 34

    The ancilla-depth tradeoff is derived for a Suzuki-based simulation architecture; whether it extends beyond product-formula architectures remains open.

    Source: §1.2 · p. 4

Abstract

from arXiv · show

Block encodings are a basic interface between quantum algorithms and linear algebra. Standard LCU constructions achieve optimal circuit depth but typically require logarithmically many ancilla qubits. We ask how much quantum workspace can be reduced without sacrificing circuit depth, and study this tradeoff from both algorithmic and lower-bound perspectives. For a Hermitian decomposition $A=\sum_{j=1}^L \alpha_j H_j$, with $\|H_j\|=1$ and $\alpha=\sum_j|\alpha_j|$, we give two coherent $\varepsilon$-approximate block-encoding constructions. The first uses one ancilla qubit and has depth $\widetilde O(L(\alpha/\varepsilon)^{o(1)})$, while the second uses $O(\log\log(\alpha/\varepsilon))$ ancillas and achieves depth $\widetilde O(L)$. For a broad Suzuki-based coherent simulation architecture, we prove an ancilla-depth tradeoff. In the polynomial-resource regime and for a constant number of coherent rounds, $\log(1/\varepsilon)\le O((\log Q)^2+2^a\log Q)$, where $Q$ is depth normalized by the number of Hamiltonian terms and $a$ is the ancilla count. Thus polylogarithmic dependence on $1/\varepsilon$ requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients $1/L$ and error $\varepsilon=\eta/L$ with fixed $0<\eta<1$, we prove $2^a=\Omega_\eta(L^2/(T+L))$, where $T$ is the number of oracle queries. Hence $a=\Omega(\log L)$ when $T=O(L^\alpha)$ for some $\alpha<2$. Moreover, in the exact case, $a\ge \log L$ regardless of $T$. We also extend this tradeoff to arbitrary nonnegative coefficients. Finally, we apply our low-ancilla constructions to normalized trace estimation in DQC1, obtaining an optimal algorithm linear in the approximate degree together with a matching query lower bound. Together, these results establish quantitative space-depth and space-query tradeoffs in two natural circuit models.

1 Introduction

Block encodings connect linear-algebraic operators to coherent quantum implementations, but their ancilla costs motivate asking how to reduce workspace without losing depth efficiency. The paper gives two low-ancilla constructions for Hermitian decompositions, using Hamiltonian simulation as a route to block encoding.

1 Introduction

  • Standard LCU block encoding uses O(log L) ancillas and depth linear in L, with ancillas coherently selecting terms through controlled operations.Reducing this workspace while retaining depth efficiency can simplify costly multi-qubit controls.Source: §1 · p. 3
  • The central question is how much workspace depth-efficient coherent block encoding requires, including whether less workspace can be traded for additional depth.Approximation may allow this tradeoff, but its quantitative form was missing.Source: §1 · p. 3
  • The paper studies the tradeoff constructively and through lower bounds, showing that reduced workspace can entail additional depth or query complexity.The resulting tradeoff is established in two natural coherent circuit models.Source: §1 · p. 3

1.1 Low-ancilla coherent block encodings

  • Using GQSP, the authors refine the Hamiltonian-simulation-to-block-encoding route to require one ancilla qubit under a weaker norm condition.This reduction is then applied to operators given by Hermitian decompositions.Source: §1.1 · p. 3
  • Using 2k-th order product formulas gives a single-ancilla block encoding, and optimizing over k determines its circuit-depth bound.The supplied passage does not state the optimized bound explicitly.Source: §1.1 · p. 3
  • Multiproduct formulas instead give a block encoding with O(log log(α/ε)) ancillas and depth eO(L).This contrasts with the single-ancilla construction's precision-dependent depth.Source: §1.1 · p. 4

1.2 Ancilla-depth tradeoff for coherent product-formula simulation

For a broad coherent simulation architecture based on Suzuki product formulas, the paper bounds how precision, normalized depth, ancilla count, and coherent rounds can trade off. Under polynomial-resource assumptions and a constant number of rounds, the bound rules out polylogarithmic precision dependence with constant ancillas within this architecture.

1.2 Ancilla-depth tradeoff for coherent product-formula simulation

  • The result is specific to Suzuki-based simulation; extending the tradeoff to general quantum circuits or beyond product-formula architectures remains open.Its relevance to block encoding follows from the close connection between Hamiltonian simulation and block encoding, with constant ancilla and logarithmic depth overhead.Source: §1.2 · pp. 4, 6
  • When 2^a ≤ √x, including constant ancilla count, the bound requires log Q = Ω(√x), where x = log(1/ε).Thus constant ancillas cannot yield polylogarithmic dependence on inverse precision in this setting.Source: §1.2 · p. 5
  • For constant s under the polynomial-resource assumptions, log(1/ε) ≤ O((log Q)^2 + 2^a log Q), relating precision to normalized depth Q and ancilla count a.The polynomial-resource conditions include s2^a ≤ Q^c0 and |η| ≥ Q^-c1.Source: §1.2 · p. 5
  • When 2^a ≥ √x, the depth obstruction weakens to log Q = Ω(x/2^a), and for a = log log(1/ε) + O(1) the bound no longer rules out polylogarithmic depth.This is consistent with the regime achieved by multiproduct formulas.Source: §1.2 · p. 6
  • The general tradeoff applies without further restrictions on Suzuki order, coherent rounds, ancilla size, refinement parameters, or controller unitaries.The architecture's controllers and refinements are chosen independently of the specific Hamiltonian terms.Source: §1.2 · pp. 4, 6
  • Approximation power comes from higher Suzuki order and coherent control; reducing ancillas requires increasing the number of rounds to maintain cancellation, which increases depth.The depth convention counts sequential Hamiltonian term-evolution slots and ignores possible additional multiplexing overhead, so it can underestimate physical depth.Source: §1.2 · pp. 4, 6

1.3 Ancilla-query tradeoffs for approximate LCU

The paper studies ancilla-query tradeoffs for repeated-query LCU circuits, where controlled queries to input unitaries are interleaved with ancilla unitaries. Approximate implementation permits some exchange between ancillas and queries, while exact implementation retains a logarithmic ancilla requirement regardless of query count.

1.3 Ancilla-query tradeoffs for approximate LCU

  • The model allows repeated queries to arbitrary input unitaries, each controlled on the all-zero ancilla state and interleaved with ancilla unitaries.T counts controlled input-unitary queries; the cost of ancilla unitaries and internal implementation of each input unitary is excluded.Source: §1.3 · p. 7
  • For balanced coefficients 1/L and error ε=η/L, T=O(L^(1+α)) queries with 0≤α<1 require 2^a=Ω_η(L^(1−α)), or a≥(1−α)log(L)−O_η(1).The setting assumes fixed η and the dimensional condition N≥T(L+1)^2, which the authors attribute to their proof technique.Source: §1.3 · pp. 7–8
  • If 2^a=O(L^β) for 0≤β<1, the balanced approximate case requires T=Ω_η(L^(2−β)) queries.The tradeoff is stated for coefficients λ_j=1/L and ε=η/L.Source: §1.3 · pp. 7–8
  • In the exact case, a≥log(L) for arbitrary T, so additional queries cannot compensate for reduced ancilla space.The paper identifies the standard LCU construction as optimal in ancilla scaling within its repeated-query circuit model.Source: §1.3 · p. 8

1.4 Relation between the two tradeoffs

The two tradeoffs apply to different circuit models: coherent Suzuki-based Hamiltonian simulation and repeated-query LCU with arbitrary unitary black boxes. Their constant-ancilla behavior differs, and neither lower bound covers unrestricted quantum circuits.

1.4 Relation between the two tradeoffs

  • The Suzuki tradeoff concerns coherent Hamiltonian simulation within a product-formula architecture; the LCU tradeoff treats constituent operators as arbitrary black boxes accessed by repeated controlled queries.The repeated queries are interleaved with ancilla unitaries.Source: §1.4 · p. 8
  • For balanced LCU with ε=η/L and constant ancillas, the repeated-query lower bound gives T=Ω_η(L^2), while Hamiltonian-simulation-based block encoding achieves eO(L^(1+o(1))) depth at the same precision scale.The paper attributes this contrast to the algebraic structure available in Hamiltonian evolution and calls the quadratic obstruction structural to generic repeated-query LCU.Source: §1.4 · p. 8
  • Neither lower bound applies to completely unrestricted quantum circuits, leaving tradeoffs in more general circuit models open.Source: §1.4 · p. 8

1.5 Technical overview of the tradeoffs

The technical overview explains the Suzuki lower bound through limits on coherent error cancellation, and the LCU lower bound through constraints on query histories and matrix rank.

1.5 Technical overview of the tradeoffs

  • Higher-order Suzuki formulas cancel low-order errors, while coherent combinations of branches can cancel additional terms; limited controller degrees of freedom prevent cancellation to arbitrarily high order.The analysis uses a Hamiltonian family whose target evolution is identity at δ=0 but has a nontrivial first-order response, which accurate simulation must reproduce.Source: §1.5 · p. 8
  • With a ancillas and s coherent reuse rounds, at most O(s2^a) branches are available for additional cancellations; derivative lower bounds and inequalities convert this constraint into the tradeoff.The proof bounds a surviving response coefficient, then combines a trigonometric Bernstein inequality with a Markov-type inequality for exponential sums.Source: §1.5 · p. 9
  • For repeated-query LCU, degree-one terms must reproduce all input unitaries while higher-degree terms remain small, constraining query histories and their overlaps.A Gram-matrix rank lower bound from nearly independent histories is compared with an upper bound from a shift-dilation representation controlled by ancilla dimension 2^a.Source: §1.5 · p. 9

1.6 An optimal quantum algorithm for normalized trace estimation in DQC1

The paper applies its few-ancilla block encoding to normalized trace estimation in DQC1. The resulting algorithm is linear in the approximate degree, with a matching query lower bound under stated assumptions.

1.6 An optimal quantum algorithm for normalized trace estimation in DQC1

  • The task is to estimate 1/N Tr[f(A)] for a continuous function f and an N=2^n dimensional log-local Hamiltonian A.Source: §1.6 · p. 9
  • The new DQC1 algorithm has complexity linear in the approximate degree of f, improving on the quadratic degree dependence arising from a Lipschitz-bound approach.The earlier approach uses quantum phase estimation; approximating f with a degree-d polynomial yields an O(d^2) Lipschitz bound by Markov brothers’ inequality.Source: §1.6 · p. 9
  • A matching linear lower bound holds in the corresponding query model under the assumptions of Theorem 6.12.Source: §1.6 · p. 9

1.7 Related work

The related work spans coherent low-ancilla approaches, space-time tradeoffs, and lower bounds for block encodings. The paper distinguishes its contribution by quantifying ancilla tradeoffs against depth or queries in coherent constructions.

1.7 Related work

  • Earlier low-ancilla approaches include expectation-value transformations, Hamiltonian representations, approximate block-encoding multiplication, and randomized methods, which differ from standard coherent block encoding.The cited work of Chakraborty et al. uses one ancilla but implements transformations through expectation-value estimation; Kang and Su maintain a Hamiltonian representation. [CHL+25]Source: §1.7 · pp. 9–10
  • Earlier quantum time-space tradeoffs addressed sorting and graph connectivity, while this paper focuses on coherent block-encoding and LCU architectures.The cited examples are [KŠdW07] for sorting and [AJPW23] for graph connectivity.Source: §1.7 · p. 10
  • The paper contrasts its coherent ancilla-depth and ancilla-query tradeoffs with prior exact-encoding lower bounds, complementary block-encoding tradeoffs, and randomized or quantum-classical LCU approaches.Prior work includes an exact Ω(log L) ancilla lower bound [CHL+25], complementary space-time and space-accuracy tradeoffs [VG25], and an LCU approach combining coherent smaller blocks with randomized sampling [WHS+25].Source: §1.7 · p. 10

Organization of the paper

  • The paper proceeds from preliminary results and a single-ancilla construction to low-ancilla algorithms, tradeoff proofs, and DQC1 normalized-trace estimation.Sections 4 and 5 prove Theorems 1.2 and 1.4, respectively; Section 6 gives the DQC1 application.Source: Organization of the paper · p. 10

2 From Hamiltonian simulation to block encoding

This section introduces block encodings and LCU, then uses generalized quantum signal processing on Hamiltonian evolution to construct a block encoding with one ancilla. The construction applies to Hermitian operators of norm at most one and has depth logarithmic in inverse error, scaled by the controlled-evolution depth.

2.1 Block encoding and LCU

  • A block encoding represents an operator as a scaled top-left block of a larger unitary, and the section uses this standard definition as its construction target.The stated definition bounds the operator-norm difference between A and the scaled ancilla-zero block by ε.Source: §2.1 · p. 11
  • Standard LCU exactly block-encodes a linear combination of L unitaries with ⌈log L⌉ ancillas and depth O(L), while exact constructions in a broad circuit model require Ω(log L) ancillas.For a Hermitian decomposition, standard LCU is not directly applicable; the section asks whether an ε-approximate encoding can use one ancilla.Source: §2.1 · p. 11

2.2 Generalized quantum signal processing

  • GQSP implements bounded Laurent polynomials of controlled evolution operators through interleaved single-ancilla rotations and controlled U or U† operations.For degree n, the cited result uses a sequence of length 2n+1; it also covers Laurent polynomials bounded on the unit circle. [MW24]Source: §2.2 · pp. 11–12

2 From Hamiltonian simulation to block encoding

  • A single-ancilla GQSP construction turns controlled Hamiltonian evolution into a coherent block encoding, under a weaker norm condition than prior reductions.The section then applies this reduction to operators given by Hermitian decompositions.Source: §2.3 · p. 12

2.3 Block encoding using Hamiltonian simulation

  • For Hermitian A with ∥A∥≤1, controlled-e±iA evolution of depth d yields a (π/2, 1, ε)-block encoding at depth O(d log(1/ε)).The construction approximates the identity x = arcsin(sin x) on [−1, 1] with a bounded Laurent polynomial, then applies GQSP.Source: §2.3 · p. 12

3 Low-ancilla block encodings for Hermitian decompositions

The section converts Hamiltonian simulation into coherent block encodings, using product formulas to trade ancilla space against precision-dependent depth. It then extends the constructions to low-ancilla QSVT.

3 Low-ancilla block encodings for Hermitian decompositions

  • One ancilla gives a coherent block encoding with subpolynomial precision dependence, while O(log log(α/ε)) ancillas yield depth Õ(L).Both constructions assume Hamiltonian simulation of each H_j costs O(1).Source: §3 · p. 13, §3.2.2 · p. 16

3.1 Single-ancilla block encodings via product formulas

  • Higher-order Trotterization produces the strictly single-ancilla construction, with depth increasing subpolynomially in the inverse precision.The construction combines GQSP with an approximate Hamiltonian evolution built from the Hermitian terms.Source: §3 · p. 13, §3.1.2 · p. 14

3.1.1 Product formulas

  • A product formula approximates evolution by composing evolutions of the individual Hermitian terms; its order controls the error as the time step shrinks.The cited error bound depends on commutator scaling and the formula’s order.Source: §3.1.1 · p. 13, §3.1 · p. 13

3.1.2 Block encoding using Trotterization

  • The Trotter-based construction combines the product-formula simulation with GQSP to encode A, assuming O(1)-cost simulation of each H_j.Its precision dependence is subpolynomial, but the construction retains exactly one ancilla.Source: §3 · p. 13, §3.1.2 · p. 14

3.2 Depth-efficient block encodings via multiproduct formulas

  • Multiproduct formulas improve precision dependence to polylogarithmic at the cost of O(log log(1/ε)) ancillas.The cited construction uses a multiproduct formula built from second-order Trotter-Suzuki steps.Source: §3.2 · p. 14, §3.2.1 · p. 14

3.2.2 Block encoding using multiproduct formula

  • The multiproduct block encoding has O(log log(α/ε)) ancillas and Õ(L) depth when each term’s Hamiltonian simulation costs O(1).The paper uses simpler commutator-scaling bounds; a cited refinement may further improve the multiproduct complexity bounds.Source: §3.2.2 · p. 16

3.3 Low-ancilla QSVT

  • Coherent block encodings can serve directly as QSVT inputs, enabling polynomial transformations of operators given by Hermitian decompositions.The Trotter-based implementation uses depth Õ(5^(k−1)Ld^(1+1/k)/ε^(1/k)); the multiproduct variant gives depth Õ(Ld) with O(log log(αd/ε)) ancillas.Source: §3.3 · pp. 16–17

4 Proof of Theorem 1.2

The proof uses the simulator’s linear response to a parameterized Hamiltonian as a witness for the architecture’s limitations. It bounds that response from below and above to establish the ancilla-depth tradeoff.

4 Proof of Theorem 1.2

  • The proof’s witness is the mismatch g(t) between simulator and target linear responses, which cannot be made arbitrarily small without sufficient ancilla space or depth.At zero parameter, the construction satisfies the zeroth-order condition exactly, so the first nontrivial necessary condition is matching linear response.Source: §4 · p. 18

4.1 A lower bound of |g(2n+1)(0)|

  • For any n ≥ k ≥ 1, the coefficient bound (2n + 1)!|c_{k,n}| ≥ e^(−O(kn + k log k)) holds; the lower-bound argument combines it with a moment estimate from Lemma 4.3.Lemma 4.3 gives an n in {k, k + 1, . . . , k + sR − 1} for which |Mn| has a lower bound.Source: §4.1 · pp. 19–20

4.2 An upper bound of |g(2n+1)(0)|

  • The upper-bound argument truncates the ideal evolution at J = O(log(1/ε)) while controlling both evolution error and its parameter derivative.It compares the simulator with the truncated evolution and uses a trigonometric-degree bound to control the derivative.Source: §4.2 · p. 21

5 Proof of Theorem 1.4

This section proves Theorem 1.4 by extending the ancilla-query lower bound to arbitrary nonnegative coefficients via effective support, deriving dimension-versus-rank constraints from query histories, and establishing an exact-case support bound independent of query count. It also bounds Frobenius norms of conjugated operators and applies Lemma 5.10.

5 Proof of Theorem 1.4

  • For arbitrary nonnegative coefficients, Theorem 5.1 gives an ancilla-query tradeoff in terms of effective support above threshold τ > ε; exactly, 2^a ≥ |supp(λ)| for any query count T.The stated approximate specialization assumes ε ≤ rτ for a fixed r < 1.Source: §5 · p. 22
  • This lower bound applies to a black-box repeated-query model uniform over arbitrary unitary inputs, not directly to the Hamiltonian-evolution constructions.The paper presents it as a structural limitation of repeated-query LCU rather than a matching lower bound for the Section 3 constructions.Source: §5 · p. 22

5.1 From approximation to query-history constraints

  • Uniform approximation makes the degree-one part of the query polynomial approximate the target and forces higher-degree parts to be small, yielding constraints on query-path transition matrices.The proof tests higher-degree components with unitaries that record the first and last logical labels, bounding the corresponding submatrices.Source: §5.1 · pp. 24–26

5.2 From query-history constraints to the ancilla lower bound

  • For K ≥ 1, the MK vectors in FK lie in C^d ⊗ C^{T+K−1}, so their Gram matrix has rank at most d(T+K−1) ≤ 2^a(T+K−1).Source: §5.2 · p. 28
  • For each 1 ≤ k < T, the proof obtains ||U†H_kU||_F ≤ K_r and applies Lemma 5.10 with κ = K_r.Source: §5.2 · p. 29

6 An optimal quantum algorithm for normalized trace estimation in DQC1

The section develops a low-ancilla DQC1 algorithm for normalized trace estimation whose cost depends linearly, up to logarithmic factors, on the approximate degree of the function. A matching query lower bound establishes optimality under the stated conditions.

6.1 An optimal quantum algorithm for normalized trace estimation

  • The task is to estimate 2^-n Tr[f(A)]; approximate degree is identified as a key parameter governing its complexity.Normalized traces of unitaries can be estimated in DQC1 using one clean qubit.Source: §6.1 · p. 29
  • The algorithm has total cost eO(αL · g degε/3(f)/ε2) and uses O(log log(α · g degε/3(f)/ε)) clean qubits.Source: §6.1 · p. 30
  • The method's cost depends linearly on approximate degree up to logarithmic factors, whereas the phase-estimation approach may incur quadratic dependence.The quadratic dependence follows by applying phase estimation to a degree-d polynomial approximant and using a Lipschitz bound of O(d2).Source: §6.1 · pp. 30–31

6.2 Lower bound analysis

  • Under Ed ≤ cEd−1, estimating τf to error γ/4 requires Ω(d) queries, with γ ≥ 2(1−2c)Ed−1.Here d is the approximate degree of f; when Ed−1 = Ω(1), constant additive error still requires Ω(d) queries.Source: §6.2 · p. 33

7 Conclusion

The conclusion presents low-ancilla block encodings as a space-depth and space-query tradeoff, with constructive results and lower bounds in the studied models. Extending analogous tradeoffs to more general circuit models remains future work.

7 Conclusion

  • The paper gives two constructions for Hermitian decompositions that reduce ancilla space at the cost of additional circuit complexity.The conclusion frames these constructions alongside lower-bound results.Source: §7 · p. 34
  • Suzuki-based coherent simulation and repeated-query LCU yield quantitative ancilla-depth and ancilla-query tradeoffs in the studied settings.With a constant number of coherent rounds and polynomial resources, constant ancilla space cannot provide polylogarithmic dependence on inverse precision within the Suzuki-based architecture.Source: §7 · p. 34
  • Analogous tradeoffs beyond the architectures considered remain an important direction for future work.The results motivate treating ancilla space as a computational resource rather than merely implementation overhead.Source: §7 · p. 34

Related papers

Loading 2607.01843v2…