Needs an explicit decomposition of the target into implementable unitaries with a known coefficient vector, and the ability to prepare a state from those coefficients. Childs, Kothari and Somma apply this route to a sparse $A$ through its associated quantum walk, so it runs from the entry oracle without Hamiltonian simulation as an intermediate. It costs more ancillas than the QSVT route, which carries the polynomial in one qubit's worth of phase shifts.

A block-encoding of $A$ together with its subnormalisation $\alpha$; a target function $f$ on $[-1,1]$; an error budget $\varepsilon$.

1. Block-encoding → Block-encodingBlock-encode a matrix

   Childs, Kothari and Somma block-encode $H := A/d$ for a $d$-sparse Hermitian $A$ of dimension $N$ with $\|A\|_{\max} \le 1$, directly from oracle access to the entries of $A$ and with no Hamiltonian simulation in between. For each row $j$ they define, on $\mathbb{C}^{2N} \otimes \mathbb{C}^{2N}$, the state $|\psi_j\rangle := |j\rangle \otimes \frac{1}{\sqrt{d}} \sum_{k \in [N] : A_{jk} \neq 0} \big( \sqrt{A_{jk}^*}|k\rangle + \sqrt{1-|A_{jk}|}\,|k+N\rangle \big)$, and the isometry $T := \sum_j |\psi_j\rangle\langle j|$ then satisfies $T^\dagger T = 1$ and $T^\dagger S T = H$ for the swap $S|j,k\rangle = |k,j\rangle$: $T$ carries $H$ exactly, with no subnormalization past the $1/d$ already folded in. assumption: the oracle is taken to return exactly $d$ nonzero entries for a given row, which the paper calls without loss of generality since zero entries can be treated as nonzero to make up the difference; and a fixed branch of the square root is used where $A_{jk}$ is complex. The walk $W := S(2TT^\dagger - 1)$ that this method's own step raises to powers costs $O(1)$ queries to that oracle.

   assumption

   Open this step

2. Block-encoding → Block-encoding of f(A)combine the Chebyshev terms, post-select

   The walk operator is what makes the Chebyshev series implementable: within the invariant subspace of an eigenvector of $H = A/d$, Childs, Kothari and Somma's Lemma 16 gives $W^n$ the diagonal entry $T_n(\lambda)$, so applying the isometry $T$, then $W^n$, then $T^\dagger$ implements $|0^m\rangle|\psi\rangle \mapsto |0^m\rangle T_n(H)|\psi\rangle + |\Phi^\perp\rangle$ in $O(n)$ queries, where $\Phi^\perp$ is annihilated by the all-zeros projector. The series is then summed by their Lemma 6: a preparation $V|0^m\rangle = (1/\sqrt{\alpha}) \sum_i \sqrt{\alpha_i}|i\rangle$ and a selection $U = \sum_i |i\rangle\langle i| \otimes U_i$ give $V^\dagger U V|0^m\rangle|\psi\rangle = (1/\alpha)|0^m\rangle M|\psi\rangle + |\Psi^\perp\rangle$. (The paper writes that operator as $W$ as well; it is not the walk above, and the collision is the source's, not a redefinition here.) assumption: The answer is the all-zeros branch and nothing else: measuring the first $m$ qubits and seeing $|0^m\rangle$ leaves the second register proportional to $M|\psi\rangle$, which happens with probability $(\|M|\psi\rangle\|/\alpha)^2$. The $1$-norm $\alpha = \sum_i \alpha_i$ of the coefficients, not the degree, is what that probability is paid in. No phase factors are computed anywhere in this: the polynomial enters through the coefficients loaded by $V$, which is the whole difference from the QSVT route across the same two states.

   assumption

A circuit implementing a block-encoding of $f(A)$ to error $\varepsilon$, together with the query count in $U$ and $U^\dagger$.

• Polynomial approximation

  Given a target function, a domain and an error $\varepsilon$, return a polynomial of definite parity, bounded on $[-1,1]$, that is $\varepsilon$-close to the target on that domain, with an explicit degree.

  This method asks here for a Chebyshev series for $1/x$, accurate to $\varepsilon$ on $D_{\kappa d} := [-1,-1/(\kappa d)] \cup [1/(\kappa d),1]$, where $\kappa$ is the condition number of $A$, $d$ its sparsity and $H := A/d$ the block-encoded matrix. Childs, Kothari and Somma reach it in three steps: Lemma 17 replaces $1/x$ by $f(x) := (1-(1-x^2)^b)/x$, which is $\varepsilon$-close to $1/x$ on $D_{\kappa d}$ for any integer $b \ge (\kappa d)^2 \log(\kappa d/\varepsilon)$; $f$ is then exactly representable in Chebyshev polynomials of order at most $2b-1$; and Lemma 19 truncates that representation at $j_0 = \sqrt{b \log(4b/\varepsilon)}$, giving a $g$ still $\varepsilon$-close to $f$, which the proof of Theorem 4 carries forward as $\|H^{-1} - g(H)\| \le \varepsilon$. approximation: the degree handed back is $O(j_0) = O(d\kappa \log(d\kappa/\varepsilon))$, and $j_0$ fixes the largest walk power the selection ranges over; the coefficient $1$-norm $\alpha$ paid for in post-selection success obeys $\alpha \le 4j_0/d$, which the paper gets from a term of its expansion being a probability and hence at most $1$.

  approximation

given  the target function, and a sparse A through its associated quantum
       walk -- the route Childs, Kothari and Somma take, which runs from
       the entry oracle without Hamiltonian simulation as an intermediate

require  an explicit decomposition of the target into implementable
         unitaries with a known coefficient vector
require  the ability to prepare a state from those coefficients

write the target function as a Chebyshev series

# no phase factors are computed: the qsp-phase-factors step is bypassed,
# and the polynomial enters through the coefficients of the combination

implement the series as a linear combination of walk-operator powers,
    using a PREPARE/SELECT pair on an ancilla register

post-select

# this route costs more ancillas than the QSVT route, which carries the
# polynomial in one qubit's worth of phase shifts

# cost, as Childs, Kothari and Somma state it in their abstract's own
# comparative terms: for a sparse, well-conditioned A the
# Harrow-Hassidim-Lloyd algorithm runs in time poly(log N, 1/epsilon), and
# theirs improves this to a running time polynomial in log(1/epsilon) --
# exponentially improving the dependence on precision "while keeping
# essentially the same dependence on other parameters". That claim is for
# the complete linear-systems algorithm this transform powers, not a
# standalone cost for the LCU step. The abstract states no closed-form
# bound; the exact statements, including the condition-number dependence,
# are in the paper's full text and are not quoted here.

Childs, Kothari and Somma state the improvement in their abstract's own comparative terms: for a sparse, well-conditioned $A$, the Harrow–Hassidim–Lloyd algorithm runs in time $\mathrm{poly}(\log N, 1/\varepsilon)$, and theirs improves this to a running time polynomial in $\log(1/\varepsilon)$ — exponentially improving the dependence on precision "while keeping essentially the same dependence on other parameters". The claim is for the complete linear-systems algorithm this transform powers, not a standalone cost for the LCU step. The abstract states no closed-form bound; the exact statements, including the condition-number dependence, are in the paper's full text and are not quoted here.

• Qualtran's ChebyshevPolynomial and LinearCombination block-encoding bloqs

  • Quantum computing enhanced computational catalysis

    Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, Matthias Troyer · 2020

  • Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

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

  About

  Google Quantum AI's Qualtran — a Python library the repository describes as "for expressing and analyzing Fault Tolerant Quantum algorithms" — ships a `ChebyshevPolynomial` block-encoding bloq whose docstring states this record's own construction: given a block encoding $\mathcal{B}[A/\alpha]$ of a Hermitian $A$ with $\|A\| \le 1$, "this bloq constructs $\mathcal{B}[T_j(A/\alpha)]$ with normalization factor 1." The reference it cites is not Childs, Kothari and Somma: "[Quantum computing enhanced computational catalysis](https://arxiv.org/abs/2007.14460). von Burg et al. 2007. Page 45; Theorem 1" — a paper by von Burg, Low, Häner, Steiger, Reiher, Roetteler and Troyer that arXiv's own abstract page dates 2020-07-28, not the "2007" the docstring prints, which reads the identifier's year digits as a publication year. For the case this record's own $H := A/d$ is — a block encoding whose normalization $\alpha \ne 1$ — the same module documents a second class, `ScaledChebyshevPolynomial`: "Unlike `ChebyshevPolynomial`, this bloq accepts $\mathcal{B}[A/\alpha]$ with $\alpha \neq 1$ and constructs $\mathcal{B}[T_j(A)]$ which is not a multiple of $\mathcal{B}[T_j(A/\alpha)]$ in general," citing a different paper again: Camps, Lin, Van Beeumen and Yang, "Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices" (arXiv:2203.10236, Section 5.1). Neither class names Childs, Kothari or Somma, and neither approximates $1/x$ or solves a linear system; what they implement is the walk-operator-power mechanism this record's own hops describe abstractly — repeated applications of a block encoding and its adjoint, interleaved with a reflection, producing a Chebyshev polynomial of the encoded matrix on the block's signal subspace, the same object Childs, Kothari and Somma's Lemma 16 reaches via $W^n \to T_n(\lambda)$ — and then, where more than one such polynomial must be combined, the PREPARE/SELECT linear-combination-of-unitaries machinery this record's own `summary` names.

  Methods

  `ChebyshevPolynomial(block_encoding, order)` builds $T_j(A/\alpha)$ by alternating the given block encoding and its adjoint around a reflection, not by any linear combination: `build_composite_bloq` loops `order // 2` times, and each pass applies `reflection_bloq` (`ReflectionUsingPrepare.reflection_around_zero(bitsizes=(self.ancilla_bitsize,), global_phase=-1)`) to the ancilla, then `block_encoding`, then the reflection again, then `block_encoding.adjoint()`; an odd order appends one more reflection-then-`block_encoding` at the end. `build_call_graph` counts `n // 2 + n % 2` calls to `block_encoding`, `n // 2` to its adjoint, and `n - n % 2` reflections. The constructor raises unless `self.block_encoding.signal_state.prepare` is `PrepareIdentity`: "Cannot take Chebyshev polynomial of block encodings with non-zero signal state." `ScaledChebyshevPolynomial`, needed whenever $\alpha \ne 1$, does not reuse that alternation directly for the rescaled case: its `linear_combination` property expands the target $T_k(\alpha x)$ in the Chebyshev basis of $x$ — `coeffs = np.polynomial.chebyshev.cheb2poly([0] * self.order + [1])`, each term then rescaled by a power of `self.block_encoding.alpha`, and converted back with `cheb_coeffs = np.polynomial.chebyshev.poly2cheb(coeffs)` — and hands those coefficients, together with the lower-order bloqs `ChebyshevPolynomial(self.block_encoding, i) for i in range(self.order + 1)`, to `LinearCombination`. That is where the PREPARE/SELECT pair lives. `LinearCombination`'s own docstring states the object it builds in this record's own language: "Builds the block encoding $B[\lambda_1 U_1 + \lambda_2 U_2 + \cdots + \lambda_n U_n]$ given block encodings $B[U_1], \ldots, B[U_n]$ and coefficients $\lambda_i \in \mathbb{R}$ ... Under the hood, this bloq uses LCU Prepare and Select oracles to build the block encoding." Its `prepare` property returns a `BlackBoxPrepare` wrapping `StatePreparationAliasSampling`, fed by `qualtran.linalg.lcu_util.preprocess_probabilities_for_reversible_sampling` on the rescaled $|\lambda_i|$; its `select` property wraps `ApplyLthBloq` over the sign-corrected block encodings in a `BlackBoxSelect`; and `build_composite_bloq` applies `self.prepare`, then `self.select`, then `self.prepare.adjoint()` on a shared ancilla — PREPARE, SELECT, PREPARE-dagger, with the target term occupying the branch this record's own hop calls the post-selected outcome. The docstring gives the same bookkeeping this record's `conditions` and hop notes state abstractly: normalization $\alpha = \sum_i |\lambda_i|\alpha_i$, ancilla count $a = \lceil \log_2 n \rceil + \max_i a_i$, and precision $\epsilon = (\sum_i |\lambda_i|)\max_i \epsilon_i$. What neither class does is approximate a target function such as $1/x$ by a truncated Chebyshev series in the first place — the coefficients `ScaledChebyshevPolynomial` computes come from a Chebyshev-of-Chebyshev rescaling identity, a fixed classical calculation, not from this record's own `polynomial-approximation` step; a caller wanting Childs, Kothari and Somma's $1/x$ series would have to supply that truncated coefficient vector separately and combine the resulting `ChebyshevPolynomial` bloqs with `LinearCombination` directly, the way `ScaledChebyshevPolynomial` already demonstrates doing for a different target.

  Data

  No dataset and no molecule. The bloq examples are single-qubit toys: `_chebyshev_poly_even` combines an `XGate` and a `Hadamard` unitary with equal weight (`LinearCombination((Unitary(XGate()), Unitary(Hadamard())), (0.5, 0.5), lambd_bits=1)`) and raises the result to order 4; `_chebyshev_poly_odd` takes a bare `Hadamard` to order 5. `_scaled_chebyshev_poly_even` and `_scaled_chebyshev_poly_odd` are the same two constructions with $\alpha \ne 1$ (the odd case built with `evolve(Unitary(Hadamard()), alpha=3.14)`). The correctness tests go further: `test_chebyshev_matrix` and the slow-marked `test_chebyshev_matrix_random` block-encode an explicit $2\times2$ matrix — first a fixed combination `(XGate + 3*Hadamard)/4`, then twenty Hermitian matrices drawn from `qualtran.linalg.matrix.random_hermitian_matrix` with `np.random.RandomState(1234)` — through a purpose-built `TestBlockEncoding.from_matrix`, which pads a $2\times2$ matrix into a $4\times4$ unitary via `MatrixGate`.

  Code

  `qualtran/bloqs/block_encoding/chebyshev_polynomial.py` (classes `ChebyshevPolynomial`, `ScaledChebyshevPolynomial`) and `qualtran/bloqs/block_encoding/linear_combination.py` (class `LinearCombination`) in https://github.com/quantumlib/Qualtran — Python, Apache-2.0 (the repository's licence field and the file headers, "Copyright 2023 Google LLC" and "Copyright 2024 Google LLC" respectively, agree). Distributed on PyPI as `qualtran`; version 0.7.0 was the release current on 2026-08-26, when this file was read from the `main` branch. The earliest commit the GitHub API returns for `chebyshev_polynomial.py` at its present path is pull request 997, "Move `block_encoding.py` into `block_encoding/` subpackage and split into multiple files" (2024-05-28), whose message describes moving and splitting a pre-existing `block_encoding.py` rather than creating the class; nothing checked here establishes when `ChebyshevPolynomial` was first written. Tests: `qualtran/bloqs/block_encoding/chebyshev_polynomial_test.py`.

  Results

  The correctness check is tensor contraction against a classical NumPy evaluation of the same Chebyshev polynomial, not execution on hardware or a named circuit simulator. Helper functions `t4(x) = 8x^4 - 8x^2 + I` and `t5(x) = 16x^5 - 20x^3 + 5x` evaluate the matrix polynomial directly; `gate_test(bloq)` builds the bloq between fixed $|0\rangle$ ancilla and resource states, calls `bloq.tensor_contract()`, and rescales by `bloq.alpha`. `test_chebyshev_poly_even_tensors` (marked `@pytest.mark.slow`) checks the order-4 combination of `XGate` and `Hadamard` against `t4` at `atol=1e-14`; `test_chebyshev_poly_odd_tensors` checks order-5 `Hadamard` against `t5` at the same tolerance; `test_chebyshev_zero_order` and `test_chebyshev_first_order` check the order-0 and order-1 edge cases return the identity and the base unitary exactly (`atol=1e-14`). `test_chebyshev_matrix` block-encodes an explicit $2\times2$ matrix through `TestBlockEncoding.from_matrix` and checks `t4` at `atol=2e-15`; the slow-marked `test_chebyshev_matrix_random` repeats this over 20 random Hermitian $2\times2$ matrices at the looser `atol=3e-8`. For the rescaled class, `test_scaled_chebyshev_even_tensors` checks `t4` applied to `(XGate + Hadamard)` — i.e. $\alpha = 2$ folded into the target rather than divided out — at the much looser `atol=0.06`, while the odd-order `test_scaled_chebyshev_odd_tensors` reaches `atol=1e-14` again. `test_scaled_chebyshev_even_cost` only calls `get_cost_value(bloq, QECGatesCost())` and asserts nothing about the returned value. Of the eight tensor- or matrix-value correctness tests in this file, four are marked `@pytest.mark.slow` and need not run in a default `pytest` invocation — `test_chebyshev_poly_even_tensors`, `test_chebyshev_matrix_random`, `test_scaled_chebyshev_even_tensors` and `test_scaled_chebyshev_odd_tensors` — while `test_chebyshev_poly_odd_tensors`, `test_chebyshev_zero_order`, `test_chebyshev_first_order` and `test_chebyshev_matrix` are not; the marking tracks neither polynomial order parity nor whether the construction routes through `LinearCombination` (`test_chebyshev_matrix` is order-4 and unmarked, while `test_scaled_chebyshev_odd_tensors` is order-5, LCU-combined, and marked). The module's own `bloq_autotester` checks (`test_chebyshev_poly_even`, `test_chebyshev_poly_odd`, `test_scaled_chebyshev_poly_even`, `test_scaled_chebyshev_poly_odd`) are unmarked but check construction and resource-counting machinery, not the encoded value.

• Linear combination of unitaries · Qiskit

  From the repository — run, not written up from a paper · native

  About

  A block-encoding primitive that turns a weighted sum of unitary operations into one larger unitary circuit.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Two-term PREPARE–SELECT–unprepare circuit checked on a one-qubit target · success branch and coefficient normalization recorded

• Linear combination of unitaries

  A block-encoding primitive that turns a weighted sum of unitary operations into one larger unitary circuit.