Chebyshev series by linear combination of unitaries

What it fills

• Matrix function

  Given a block-encoding of $A$ and a target function $f$ bounded on $[-1,1]$, produce a circuit whose designated block is an $\varepsilon$-approximation of $f$ applied to the singular values (or eigenvalues) of $A$.

When it applies

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.

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• 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

Example

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.

Cost, as the source states it

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.

Implementations

• Qualtran's ChebyshevPolynomial and LinearCombination block-encoding bloqs

  • Quantum computing enhanced computational catalysis
  • Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

  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.

  `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.

  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`.

  `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`.

  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.

What it needs

1. Block-encode a matrix 4 methods

   Wrap an operator $A$ inside a larger unitary $U$ so that $A/α$ sits in $U$'s top-left block, giving every routine above it one uniform way to touch the matrix. The subnormalization $α$ and the ancilla count are outputs of this layer, not free parameters.

Slots it makes unnecessary

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

• QSP phase factors

  Given an admissible polynomial, compute the phase sequence $Φ$ that makes the quantum-signal-processing product reproduce it to accuracy $\varepsilon$ in classical finite-precision arithmetic.

Other ways to fill the same slot

Different approaches

• Quantum singular value transformation

  Interleave the block-encoding $U$, its inverse, and projector-controlled phase shifts $e^{iφ(2Π-I)}$ so that the designated block becomes $P$ applied to the singular values of $A$. The phase sequence is the compiled form of the polynomial, and a single ancilla qubit carries the phase shifts.

In the Atlas

• Linear combination of unitaries

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

Sources

• Hamiltonian Simulation Using Linear Combinations of Unitary Operations↗Andrew M. Childs, Nathan Wiebe · 2012theory yes · simulation ? · hardware no
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision↗Andrew M. Childs, Robin Kothari, Rolando D. Somma · 2015theory yes · simulation no · hardware no