The Quantum Singular Value Transformation (QSVT) provides a powerful framework with the potential for quantum speedups across a wide range of applications. Its core input model is the block encoding framework, in which non-unitary matrices are embedded into larger unitary matrices. Because the gate complexity of the block-encoding subroutine largely determines the overall cost of QSVT-based algorithms, developing new and more efficient block encodings is crucial for achieving practical quantum advantage. In this paper, we introduce a novel method for constructing quantum circuits that block encode linear combinations of Pauli strings. Our approach relies on two key components. First, we apply a transformation that converts the Pauli strings into pairwise anti-commuting ones, making the transformed linear combination unitary and thus directly implementable as a quantum circuit. Second, we employ a correction transformation based on the stabilizer formalism which uses an ancilla register to restore the original Pauli strings. Our method can be implemented with an ancilla register whose size scales logarithmically with the number of system qubits. It can also be extended to larger ancilla registers, which can substantially reduce the overall quantum circuit complexity. We present four concrete examples and use numerical simulations to compare our method's circuit complexity with that of the Linear Combination of Unitaries (LCU) approach. We find that our method achieves circuit complexities comparable to or better than LCU, with possible advantages when the structure of the target operators can be exploited. These results suggest that our approach could enable more efficient block encodings for a range of relevant problems extending beyond the examples analyzed in this work.
The Quantum Singular Value Transformation (QSVT) provides a powerful framework with the potential for quantum speedups across a wide range of applications. Its core input model is the block encoding framework, in which non-unitary matrices are embedded into larger unitary matrices. Because the gate complexity of the block-encoding subroutine largely determines the overall cost of QSVT-based algorithms, developing new and more efficient block encodings is crucial for achieving practical quantum advantage. In this paper, we introduce a novel method for constructing quantum circuits that block encode linear combinations of Pauli strings. Our approach relies on two key components. First, we apply a transformation that converts the Pauli strings into pairwise anti-commuting ones, making the transformed linear combination unitary and thus directly implementable as a quantum circuit. Second, we employ a correction transformation based on the stabilizer formalism which uses an ancilla register to restore the original Pauli strings. Our method can be implemented with an ancilla register whose size scales logarithmically with the number of system qubits. It can also be extended to larger ancilla registers, which can substantially reduce the overall quantum circuit complexity. We present four concrete examples and use numerical simulations to compare our method's circuit complexity with that of the Linear Combination of Unitaries (LCU) approach. We find that our method achieves circuit complexities comparable to or better than LCU, with possible advantages when the structure of the target operators can be exploited. These results suggest that our approach could enable more efficient block encodings for a range of relevant problems extending beyond the examples analyzed in this work.
Block Encoding (BE) is a crucial subroutine in many modern quantum algorithms, including those with near-optimal scaling for simulating quantum many-body systems, which often rely on Quantum Signal Processing (QSP). Currently, the primary methods for constructing BEs are the Linear Combination of Unitaries (LCU) and the sparse oracle approach. In this work, we demonstrate that QSP-based techniques, such as Quantum Singular Value Transformation (QSVT) and Quantum Eigenvalue Transformation for Unitary Matrices (QETU), can themselves be efficiently utilized for BE implementation. Specifically, we present several examples of using QSVT and QETU algorithms, along with their combinations, to block encode Hamiltonians for lattice bosons, an essential ingredient in simulations of high-energy physics. We also introduce a straightforward approach to BE based on the exact implementation of Linear Operators Via Exponentiation and LCU (LOVE-LCU). We find that, while using QSVT for BE results in the best asymptotic gate count scaling with the number of qubits per site, LOVE-LCU outperforms all other methods for operators acting on up to ≲ 11 qubits, highlighting the importance of concrete circuit constructions over mere comparisons of asymptotic scalings. Using LOVE-LCU to implement the BE, we simulate the time evolution of single-site and two-site systems in the lattice φ 4 theory using the Generalized QSP algorithm and compare the gate counts to those required for Trotter simulation.
Quantum circuits naturally implement unitary operations on input quantum states. However, non-unitary operations can also be implemented through "block encodings", where additional ancilla qubits are introduced and later measured. While block encoding underlies a host of well-established theoretical applications, its implementation in practice has been prohibitively expensive for current quantum hardware. In this paper, we present practical and explicit block encoding circuits implementing matrix polynomial transformations of a target matrix. With standard approaches, block-encoding a degree-d matrix polynomial requires a circuit depth scaling as d times the depth for block-encoding the original matrix alone. By leveraging the recently introduced Fast One-Qubit Controlled Select Linear Combination of Unitaries (FOQCS-LCU) framework, we show that the additional circuit-depth overhead required for encoding matrix polynomials can be reduced to scale linearly in d with no dependence on system size or the cost of block encoding the original matrix. Moreover, we demonstrate that the FOQCS-LCU circuits and their associated matrix polynomial transformations can be controlled with negligible overhead, enabling efficient applications such as Hadamard tests. Finally, we provide explicit hardware-efficient circuits for representative non-unitary operators, namely quantum spin models, together with detailed non-asymptotic gate counts and circuit depths.
We determine the non-Clifford T-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an n-qubit operator with a clean ancillas and at most sT gates can be compressed to use at most min{a,n+2s} ancillas, without increasing the absolute error or T-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error ε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log(n4/ε)), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on n spins, we obtain independent lower bounds Ω(n) from stabilizer nullity and Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log(1/ε)). As an application, we evaluate the T-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation T-count scales as the query count times the optimal T-count per query.
Block-encoding operators are one of the essential components in quantum algorithms based on Quantum Signal Processing. Their gate complexity largely determines the overall gate complexity of the full algorithm. Using variational methods, we compile single-ancilla block-encoding unitaries with near-optimal resource requirements for a large range of input matrices. We find that the number of variational parameters in the parameterized quantum circuit approaches the number of free parameters in the input matrices, depending on whether they are real, complex and/or hermitian. Additionally, symmetries present in the input matrix can be incorporated into the ansatz circuit, reducing the parameter count further and enhancing optimizability. While performing a variational compilation of block-encodings ceases to be computationally feasible for large system sizes, the constructed operators can be used as components of larger block-encodings via a linear combination of block-encodings.
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=∑j=1LαjHj, with ∥Hj∥=1 and α=∑j∣αj∣, we give two coherent ε-approximate block-encoding constructions. The first uses one ancilla qubit and has depth O(L(α/ε)o(1)), while the second uses O(loglog(α/ε)) ancillas and achieves depth 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/ε)≤O((logQ)2+2alogQ), where Q is depth normalized by the number of Hamiltonian terms and a is the ancilla count. Thus polylogarithmic dependence on 1/ε requires more than constantly many ancillas within this architecture. In a separate repeated-query LCU model, for balanced coefficients 1/L and error ε=η/L with fixed 0<η<1, we prove 2a=Ωη(L2/(T+L)), where T is the number of oracle queries. Hence a=Ω(logL) when T=O(Lα) for some α<2. Moreover, in the exact case, a≥logL 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.
Linear combination of unitaries (LCU) is a fundamental primitive in quantum algorithms, whose cost is typically governed by the most expensive unitary appearing in the combination. We develop a transducer-based LCU framework that reduces this worst-case dependence to a weighted average query complexity, when the constituent unitaries share access to a common set of primitive oracles.
Consider A=∑jcjUj, where cj>0 and each unitary Uj can be implemented using Cj primitive queries. Given an upper bound a≥∥A∥, our algorithm implements a block-encoding of A/α with rescaling factor α=O(a), using O(Cmax+Cλ/a) primitive queries, where λ=∑jcj, Cmax=maxjCj, and C=∑jcjCj/λ. By comparison, the standard LCU construction requires O(Cmaxλ/a) primitive queries. The improvement can therefore be substantial when costly unitaries have small weights and λ/a is large. As applications, we obtain improved block-encodings of sparse matrices, leading to quantum algorithms for sparse Hamiltonian simulation and quantum linear systems with near-optimal query complexity up to polylogarithmic factors in all relevant parameters.
Our main technique is the transducer framework developed by Belovs, Jeffery, and Yolcu [Quantum, 8:1444 (2024)]. Here we develop a complementary operator-level theory tailored to block-encodings. We identify the resolvent norm K as a key complexity measure for transducer implementation besides the existing catalyst complexity. We show that the transducer action can be converted into an ε-approximate block-encoding using only O(Klog(1/ε)) queries to the transducer, improving the precision dependence from polynomial to logarithmic.