Practical block encodings of matrix polynomials that can also be trivially controlled

arXiv:2601.18767 · quant-ph · Submitted 2026-01-26 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Practical block encodings of matrix polynomials that can also be trivially controlled".

Mira: Block encoding techniques are presented as practical tools for implementing matrix polynomial transformations in quantum circuits, overcoming previous limitations regarding circuit depth and control complexity.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, Mira and I have been looking at this paper, "Practical block encodings of matrix polynomials that can also be trivially controlled," and it seems to tackle a real problem in making quantum simulations more practical on current hardware by reducing circuit depth.

Mira: It does sound like they are focusing on taking complex transformations involving non-unitary operators and turning them into something much more manageable, which is interesting because those kinds of operations are often what we need for things like time evolution approximations or calculating certain expectation values.

Lev: From my perspective as someone thinking about real hardware, the main concern with these block encodings is always the overhead in terms of gate count and connectivity; I'm curious if they've managed to keep that overhead from ballooning uncontrollably as the system gets bigger.

Kai: Well, it looks like their summary points out a big win: they show that encoding a degree-d matrix polynomial scales linearly with d, which means the extra depth for the polynomial is independent of how complicated the original block encoding of H is and also independent of system size.

Mira: That independence from system size is what really caught my attention; it suggests a scaling relationship that doesn't explode when you scale up your physical qubit count, which is exactly what we need for scaling up simulations.

Lev: If the depth scales linearly with d, that’s a lot better than what we see in some QSVT-based implementations where the depth goes proportional to the product of d and n; that multiplicative scaling would be much harder to handle on current machines.

Kai: And they also mention something about controlling this entire block encoding for the polynomial using just four CNOT gates, which is independent of both system size and the degree of the polynomial. That seems like a significant reduction in control complexity.

Mira: Four CNOT gates being sufficient to control the entire block-encoding for a matrix polynomial is quite striking; it suggests that controlling these encodings isn't a major bottleneck at all, which is good because controlling these ancilla states often adds substantial complexity.

Title and authors: Lev: That would make running algorithms that involve estimating things like Loschmidt echo much more feasible on real hardware because the control cost stays low even for higher-degree polynomial approximations.

Kai: The paper also shows they can implement these block encodings efficiently using only local gates—nearest-neighbor and single-qubit gates—on a two-dimensional square grid architecture, with the increase in circuit depth just being a few layers regardless of the system size.

Mira: That mapping to a 2D square grid is practical because it aligns well with how we build many physical quantum processors today, and keeping that overhead constant across system sizes is crucial for practical implementation <ref:2601.18767#pg0>.

Lev: If they can map the circuits efficiently to local gates, it suggests that the resource requirements for running these matrix polynomial evaluations will be much more predictable when moving from theoretical models to actual superconducting circuits.

Kai: They also detail how they can control the entire circuit by exploiting a specific assumption, Assumption one which simplifies things down to just controlling the first and last Ry rotations of POLYR and POLY†L under certain conditions <ref:2601.18767#pg0>.

Mira: That simplification is clever because it drastically reduces what needs to be controlled; instead of managing the whole block encoding, you only need to manage those two specific rotations for full control.

Lev: That reduction in the required control structure makes the error correction side of things much less demanding when we try to implement these routines on actual noisy hardware.

Kai: So, looking at these improvements, it seems like this paper offers a path toward more efficient methods for handling matrix polynomial transformations in simulations, especially those related to time evolution or estimating expectation values.

Mira: I think the implication here is that we can tackle higher-degree polynomial approximations for quantum dynamics without immediately hitting the scaling walls we usually encounter when dealing with complex unitary encodings.

Title and authors: Lev: For error correction researchers, this means that the overhead associated with setting up these state preparation oracles isn't going to be a primary blocker for running algorithms on near-term devices.

Kai: Overall, this paper seems to provide a concrete set of constructions that show how we can actually build these transformations on hardware using only local gates and keeping the control cost low.

Mira: I think the practical aspect of providing explicit circuit constructions mapped to 2D architectures is what makes this work so compelling for anyone trying to move theory into experimental reality <ref:2601.18767#pg0>.

Lev: It’s important that they provide those exact CNOT counts and depths, because without those non-asymptotic numbers, we can't really assess the real-world feasibility of putting this on a physical chip right now.

Kai: So, to wrap up our discussion on "Practical block encodings of matrix polynomials that can also be trivially controlled," it seems they have provided a framework where circuit depth scales linearly with the polynomial degree, and control overhead remains minimal.

Mira: The overall implication is that we gain a scalable method for evaluating these matrix transformations without incurring massive computational penalties due to encoding complexity or system size.

Lev: I think for error correction, this means we can focus our efforts on mitigating errors from the core physical process rather than being completely bogged down by the overhead of implementing the linear algebra itself.

Kai: We're definitely excited about how this paper shows a way to make these non-unitary operations much more accessible for quantum simulations on existing hardware platforms.

Mira: It's a solid piece of work because it connects the theoretical machinery of block encodings with a practical, low-depth circuit realization that respects the constraints of current qubit architectures.

Lev: I agree; seeing these concrete resource analyses is what moves this from just an interesting theoretical concept to something we can actually plan for in our labs.

Kai: So, as we wrap up our chat on "Practical block encodings of matrix polynomials that can also be trivially controlled," we see a clear direction for how to implement these transformations with much lower overhead.

The paper's summary: Kai: So, this paper is all about how they developed a new block encoding technique called FOQCS-LCU that makes implementing matrix polynomial transformations much more efficient by reducing circuit depth and control complexity.

Mira: That's the big picture, Kai; it seems they've found a way to structure these complex quantum operations so that the required circuit depth scales only linearly with the degree of the polynomial, which is a massive improvement over what we see in other methods.

Lev: From an error correction standpoint, that linear scaling with degree rather than something multiplicative with system size is what we need; it means we can tackle higher-degree approximations without immediately hitting resource walls.

Kai: Exactly, and they show how you can control the entire block encoding for these polynomials using just four CNOT gates, which is independent of both the system size and the polynomial degree itself.

Mira: That's a pretty remarkable result; controlling that whole structure with such a small constant overhead suggests that we can treat these encodings as almost trivial to manage once you use this specific formalism.

Lev: If we can control it with just four CNOTs, the error budget for implementing the encoding itself becomes much more manageable when we consider noise on near-term hardware.

Kai: It also showed they can map these circuits onto a 2D square grid using only local gates, and the depth overhead stays low regardless of how big the system gets <ref:2601.18767#pg0>.

Mira: That mapping to a fixed-overhead local gate architecture is very practical for experimentalists because it fits well with current superconducting circuit designs.

Lev: But what about the assumptions they made? I want to know what constraints are really on these results so we can tell if this holds up when we introduce real noise and connectivity limitations.

Kai: Well, they rely on Assumption one which simplifies controlling the whole thing down to just managing the first and last rotation gates of their state preparation oracles under specific conditions.

Mira: That assumption is key; it’s what lets them simplify the control problem significantly, but we need to verify that those specific eigenstate properties actually hold up robustly in a noisy environment.

Lev: So, they’ve shown a path to implementing matrix polynomial evaluations with controlled overhead that scales nicely with the polynomial degree and system size remains manageable on 2D lattices <ref:2601.18767#pg0>.

Kai: That's right; it basically gives us a blueprint for running simulations of time evolution approximations or estimating Loschmidt echo without the circuit depth exploding.

Mira: The real impact here is that it makes complex non-unitary dynamics accessible for simulation, which could open up new avenues in studying quantum systems with strong interactions.

Lev: If this holds up under rigorous error analysis, it’s going to be a powerful tool for testing how well we can approximate physical processes using these polynomial expansions on actual hardware.

Kai: So, the takeaway is that this block encoding framework offers a scalable and low-overhead method for handling matrix polynomials in quantum simulations.

Mira: It’s definitely a significant step because it links the abstract mathematics of block encodings directly to practical, resource-conscious circuit implementations on current architectures.

Lev: We should keep an eye on how these specific CNOT gate counts translate when we start adding actual noise models and connectivity constraints to see how resilient this framework is.

The paper's improvements: Kai: This segment focuses on the practical improvements the authors suggest for implementing these matrix polynomial transformations using their FOQCS-LCU block encoding method.

Mira: The core improvement is demonstrating how to control an entire block encoding circuit with very minimal overhead, specifically showing that controlling it takes just four extra CNOT gates for a general non-unitary matrix, or four extra CNOTs for the full polynomial approximation.

Lev: That's huge because it shows that the complexity of controlling the encoding isn't tied to system size or the degree of the polynomial in a scaling way; it stays constant regardless.

Kai: So, they suggest that by exploiting Assumption one which relates to how specific eigenstates behave, you only need to manage those first and last rotation gates for full circuit control.

Mira: That simplifies things immensely because it means you don't have to manage the entire state preparation oracle; you just focus on those two critical components for the necessary control.

Lev: If we can reduce the control complexity to such a fixed, low number of CNOTs, it drastically lowers the barrier for running these algorithms on current noisy hardware.

Kai: It also shows that when mapping this to a 2D square grid architecture, you only get an increase in circuit depth of just a few layers, no matter how large the physical system becomes <ref:2601.18767#pg0>.

Mira: That fixed overhead across system sizes is what makes the implementation strategy robust; it means we can predict the resource cost even when scaling up.

Lev: For error correction protocols, this predictability is vital; knowing exactly how many extra CNOTs are needed to set up a specific transformation helps us design better error mitigation strategies.

Kai: The implication is that for simulating non-unitary dynamics, like those from spin Hamiltonians, we can use these polynomial approximations with much lower gate counts than methods requiring QSVT.

Mira: It means we can explore higher-degree polynomial approximations of time evolution more thoroughly because the computational cost doesn't skyrocket due to encoding complexity.

Lev: This points toward a future where QPE routines for non-unitary operators become much more feasible on near-term quantum devices than previously thought possible.

Kai: So, we can expect this to lead to better simulation capabilities for complex quantum systems that involve non-unitary evolution and high-degree polynomial approximations.

Conclusion: Kai: So we're wrapping up our discussion on "Practical block encodings of matrix polynomials that can also be trivially controlled," which showed how to implement complex transformations with reduced depth and control overhead.

Mira: It really does demonstrate a way to make these high-degree polynomial operations much more feasible for quantum simulation by keeping the circuit complexity manageable.

Lev: For error correction, this is promising because lower control overhead means less noise budget is spent on setting up the encoding itself, which simplifies our error analysis.

Kai: Exactly; it’s about making simulations of time evolution and other non-unitary dynamics more practical for near-term hardware by reducing those scaling issues we usually see.

Mira: The implication is that we can tackle more intricate quantum models without immediately being constrained by the exponential scaling associated with encoding methods.

Lev: If these results hold up under realistic noise conditions, it could significantly speed up the development of algorithms for simulating complex materials where non-unitary effects are important.

Kai: We've seen concrete constructions mapped to 2D lattices and low gate counts, so this isn't just theory; it’s something we can start thinking about building and cooling on actual hardware <ref:2601.18767#pg0>.

Mira: I agree; the resource analysis tables they provided really ground these claims in reality by giving us explicit numbers for CNOT depth and control gates.

Lev: I think for the error correction community, this offers a new toolset for designing more efficient QPE routines when dealing with matrix polynomial operators that arise from physical models.

Kai: So, it seems like this paper provides a solid framework to move these non-unitary linear algebra tasks into the realm of practical quantum computation.

Mira: It's a major step forward because it bridges the gap between abstract mathematical formalism and low-depth circuit realization on current qubit platforms.

Lev: I'm still looking forward to seeing how researchers apply this framework when dealing with larger system sizes and more realistic noise models, which is where we can really test its limits.

Technical University of Munich · Department of Computer Science, KU Leuven, University of Leuven · Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory · Google Quantum AI

quant-ph

Submitted: 2026-01-26

Updated: 2026-10-06

Comments: 31 pages, 10 figures, 5 tables

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: Block encoding techniques are presented as practical tools for implementing matrix polynomial transformations in quantum circuits, overcoming previous limitations regarding circuit depth and control

Key concepts

FOQCS-LCU
This is a specific block encoding formalism that expresses a target matrix as a linear combination of unitaries, particularly Pauli strings. It uses state-preparation oracles like PR and PL to efficiently prepare necessary states, overcoming exponential overheads found in simpler methods.
Block Encoding
This technique represents the target matrix H as a structured block of unitaries rather than encoding it directly. By using this structure, the circuit depth required to implement transformations involving H is reduced, making complex matrix polynomial calculations more feasible.
Matrix Polynomial Realization
The paper generalizes block encoding to represent functions like pd(H) = a0I + a1H + ... + adHd. This is achieved by embedding the encodings of individual matrix powers (Hk) within an outer layer that encodes the polynomial coefficients using simple unary encoding on ancilla qubits.
Controlling Block Encodings
This refers to the process of applying operations to the encoded block structure. The paper shows that by exploiting specific factorization properties (Assumption 1), controlling the entire circuit simplifies drastically, often requiring only control over the first and last rotations of certain components.

Terminology

Summary

Block encoding techniques are presented as practical tools for implementing matrix polynomial transformations in quantum circuits, overcoming previous limitations regarding circuit depth and control complexity. The core finding demonstrates that leveraging the Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework allows for a reduction in circuit depth scaling linearly with the polynomial degree, independent of system size or the cost of encoding the original matrix, while enabling negligible overhead for controlling these encodings.

Key Findings and Reductions

The paper resolves several bottlenecks in block encoding:

  1. The additional circuit-depth overhead required for encoding a degree-d matrix polynomial in H relative to just H scales only with d, meaning the extra depth for the polynomial is independent of the complexity of the original block encoding of H and therefore also independent of system size.

  2. The entire block-encoding for the polynomial can be controlled by adding just 4 CNOT gates, independent of system size and of the polynomial degree.

  3. For important classes of non-unitary operators H, including 1D quantum spin models, the overall CNOT depth scales as a sum c1n + c2d. This contrasts with QSVT-based implementations which would entail a circuit depth proportional to the product d · n.

FOQCS-LCU Formalism and Block Encoding

The paper utilizes the FOQCS-LCU block encoding, which expresses the target matrix H as a linear combination of unitaries, specifically Pauli strings. This formalism involves defining state-preparation oracles, PR and PL, which utilize Dicke states preparation to achieve efficient implementations despite potential exponential overheads in naive approaches. The high-level circuit structure involves a central SELECT oracle, consisting of two parallel layers of CNOT and CZ gates.

Controlling Block Encodings

A major focus is on controlling these block encodings. The paper shows that controlled applications can be simplified by exploiting the factorization into PR, SELECT, and P†L oracles. Specifically:

  1. Controlling a unitary U applied to a specific common eigenstate ξ⟩ can be done with negligible overhead compared to its non-controlled implementation.

  2. For FOQCS-LCU block encodings, controlling the entire circuit is simplified by exploiting Assumption 1, which states that the oracles PR and PL admit unitary decompositions where P˜R and P˜L have the all-zero state 0⟩2n as an eigenstate corresponding to eigenvalue 1. This leads to a simplified construction where controlling the entire circuit requires controlling only the first and last Ry rotations of POLYR and POLY†L, respectively.

Matrix Polynomial Realization

The paper generalizes this approach to matrix polynomials, such as pd(H) = a0I + a1H + a2H2 + · · · + adHd. This is achieved by embedding the block encodings of Hk (matrix powers of H) within an outer LCU layer that encodes the polynomial coefficients ak using unary encoding on d ancilla qubits. The state-preparation oracles POLYR and POLYL are constructed using rotations and phase gates, which can be efficiently realized through specific circuits like Ry(θ0) CRy(θd−1 1) P(ϕd−1 0) for POLYR.

Practical Implementation on Hardware

The paper provides explicit circuit constructions in terms of single- and two-qubit gates assuming all-to-all connectivity, and then maps these to a two-dimensional square grid architecture using only local (nearest-neighbor and single-qubit) gates. This mapping incurs only a small overhead—the increase in circuit depth is just a few layers, independent of the system size. The resource analysis tables show that for representative spin models like the one-dimensional XYZ Heisenberg Hamiltonian, controlling the full block encoding incurs only two additional CNOT gates, and controlling the matrix polynomial circuit incurs an overhead of just 2 controlled single-qubit rotations, corresponding to a total of 4 extra CNOT gates.

Applications

The framework is shown to be particularly well-suited for Hadamard tests, which can estimate the expectation value ⟨φHφ⟩ by controlling the entire block encoding circuit while initializing and post-selecting the ancilla qubits in the state 0⟩2n. For spin models considered, this control costs only two additional CNOT gates. Furthermore, time evolution under a Hamiltonian can be approximated by a degree-d polynomial pd(H), and estimating the Loschmidt echo g(t) can be done by controlling the block encoding of pd(H) with an overhead of just four additional CNOT gates. This demonstrates that FOQCS-LCU significantly reduces control costs associated with Quantum Phase Estimation (QPE) routines.

Improvements for AI systems

As a fastidious researcher, I have analyzed this paper, Practical block encodings of matrix polynomials that can also be trivially controlled, which introduces a framework based on the Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) for efficiently implementing non-unitary matrix polynomial transformations.

Based on the findings presented in Sections V and VI, here are the specific improvements that can be made to AI systems:

The paper enables a significant reduction in computational overhead (CNOT depth) and circuit complexity for linear algebra operations involving quantum states, particularly those modeled by spin Hamiltonians. The primary improvements are centered around making complex quantum algorithms more feasible on near-term hardware by minimizing gate count while maintaining high fidelity.

Here are the specific improvements and capabilities:

  1. The ability to implement matrix polynomial transformations of a target matrix (e.g., time evolution approximations, as discussed in Section IV B) with a circuit depth scaling linearly with the polynomial degree, independent of system size or original matrix complexity.

  2. The capability to perform Hadamard tests on these block-encoded operations with negligible overhead (only 2 extra CNOT gates for general non-unitary matrices, or 4 extra CNOT gates for matrix polynomials).

  3. The demonstration that all controlled block encodings can be implemented in low-depth circuits using only nearest-neighbor two-qubit gates on a two-dimensional square lattice architecture, with the circuit depth overhead remaining constant regardless of the system size.

  4. The ability to control the entire matrix polynomial circuit (for time evolution approximations) with a trivial overhead of four additional CNOTs by controlling only the first and last rotation gates of the state preparation oracles under specific assumptions (Assumption 1).

The improved AI systems resulting from these advancements can perform the following specific tasks:

  1. A quantum machine learning system capable of simulating complex, non-unitary quantum dynamics (like those derived from spin Hamiltonians) with a significantly reduced gate count compared to traditional methods (e.g., QSVT). This allows for more complex and deeper time evolution approximations in quantum simulation algorithms.

  2. A robust method for performing Quantum Phase Estimation (QPE) routines on near-term hardware, specifically for estimating the expectation value of non-unitary operators or matrix polynomials that arise in these simulations, with a controlled overhead that is linear in the degree of the polynomial rather than scaling multiplicatively with system size.

  3. A quantum algorithm for performing Hadamard tests to extract specific real or imaginary parts of complex expectation values (like Loschmidt echo) associated with non-unitary evolution operators, making these measurements practical on current hardware.

  4. A highly efficient quantum linear algebra subroutine for matrix polynomial evaluation, which is crucial for tasks like solving differential equations approximated by polynomial expansions in quantum simulation, providing a scalable method to handle high-degree matrix transformations without exponential scaling in circuit depth relative to the degree of the transformation.

Sources

Related papers