Skip to content

Block-encodings

Rough overview (in words)

In a quantum algorithm, the quantum gates that are applied to quantum states are necessarily unitary operators. However, one often needs to apply a linear transformation to some encoded data that is not represented by a unitary operator, and furthermore one generally needs coherent access to these non-unitary transformations. How can we encode such a non-unitary transformation within a unitary operator? Block-encoding is one method of providing exactly this kind of coherent access to generic linear operators. Block-encoding works by embedding the desired linear operator as a suitably normalized block within a larger unitary matrix, such that the full encoding is a unitary operator, and the desired linear operator is given by restricting the unitary to an easily recognizable subspace. To be useful for quantum algorithms, this block-encoding unitary must also be realized by some specific quantum circuit acting on the main register and additional ancilla qubits.

Block-encodings are ubiquitous within quantum algorithms, but they have both benefits and drawbacks. They are easy to work with, since one can efficiently perform manipulations of block-encodings, such as taking products or convex combinations. On the other hand, this improved working efficiency comes at the cost of having more limited access. For example, if a matrix is stored in classical random access memory, the matrix entries can be explicitly accessed with a single query to the memory, whereas if one only has access to a block-encoding of the matrix, estimating a matrix entry to precision \(\varepsilon\) requires \(\mathcal{O}\left( 1/\varepsilon \right)\) uses of the block-encoding unitary in general (by utilizing an amplitude estimation subroutine).

Block-encodings also provide a layer of abstraction that assists in the design and analysis of quantum algorithms. One can simply assume access to a block-encoding and count the number times it is applied. To run the algorithm, it is necessary to choose a method for implementing the block-encoding. There are many ways of constructing block-encodings that could be suited to the structure of the input. For instance, there are efficient block-encoding strategies for density matrices, positive operator-valued measures (POVMs), Gram matrices, sparse-access matrices, matrices that are stored in quantum data structures, structured matrices, and operators given as a linear combination of unitaries (with a known implementation). We discuss these constructions below. For unstructured, dense matrices, the strategy for Gram matrices can be instantiated using state-preparation and quantum random access memory (QRAM) as subroutines. For more details on a particular block-encoding scheme for loading matrices of classical data, see block-encoding matrices of classical data.

Rough overview (in math)

Our goal is to build a unitary operator that gives coherent access to an \(M\times M\) matrix \(A\) (we will later relax the assumption that \(A\) is square), with normalization \(\alpha \geq \nrm{A}\), where \(\nrm{A}\) denotes the spectral norm of \(A\). As the name suggests, block-encoding is a way of encoding the matrix \(A\) as a block in a larger unitary matrix:

\[\begin{aligned} &\ \ \ \ \ \ \ \ \ \ \ \ \ \ket{0}^{\otimes a}\ket{0}^{\otimes a}_\perp\\ U_A=&\begin{aligned} \ket{0}^{\otimes a}\\ \ket{0}^{\otimes a}_\perp \end{aligned}\begin{pmatrix} A/\alpha & \cdot \\ \cdot & \cdot \end{pmatrix} \end{aligned}\]

More precisely, we say that the unitary \(U_A\) is an \((\alpha, a, \epsilon)\)-block-encoding of the matrix \(A\in\mathbb{C}^{M\times M}\) if

\[\begin{equation} \label{eq:BEDef} \left\lVert A - \alpha (\bra{0}^{\otimes a} \otimes I )U_A(\ket{0}^{\otimes a} \otimes I)\right\rVert \leq \epsilon, \end{equation}\]

where \(a\in\mathbb{N}\) is the number of ancilla qubits used for embedding the block-encoded operator, and \(\alpha,\epsilon\in\mathbb{R}_+\) define the normalization and error, respectively. Note that \(\alpha\geq \nrm{A}-\epsilon\) is necessary for \(U_A\) to be unitary. The definition above can be extended for general matrices, though additional embedding or padding may be needed (e.g., to make the matrix square).

Once a block-encoding is constructed, it can be used in a quantum algorithm to apply the matrix \(A\) to a quantum state by applying the unitary \(U_A\) to the larger quantum system. The application of the block-encoding can be thought of as a probabilistic application of \(A\): applying \(U_A\) to \(\ket{0}^{\otimes a}\ket{\psi}\) and postselecting on the first register being in the state \(\ket{0}^{\otimes a}\) gives an output state proportional to \(A\ket{\psi}\) in the second register.

There are several ways of implementing block-encodings based on the choice of matrix \(A\) [1, Section 4.2]:1

  • Unitary matrices are \((1,0,0)\)-block-encodings of themselves. Controlled unitaries (e.g. \(\mathrm{CNOT}\)) are essentially \((1,1,0)\)-block-encodings of the controlled operation.
  • Given an \(s\)-qubit density matrix \(\rho\) and an \((a+s)\)-qubit unitary \(G\) that prepares a purification of \(\rho\) as \(G\ket{0}^{\otimes a}\ket{0}^{\otimes s}=\ket{\rho}\) (s.t. \(\text{tr}_a \ket{\rho}\!\bra{\rho}=\rho\), where \(\text{tr}_a\) denotes trace over the first register), then the operator [2]
    \[\begin{equation} (G^\dagger\otimes I_s)(I_a\otimes \mathrm{SWAP}_s)(G\otimes I_s) \end{equation}\]

    is a \((1, a+s, 0)\)-block-encoding of the density matrix \(\rho\), where \(I_x\) denotes the identity operator on a register with \(x\) qubits, and \(\mathrm{SWAP}_s\) denotes the operation that swaps two \(s\)-qubit registers [1, Lemma 45]. - Similarly, one can construct block-encodings of POVM operators, given access to a unitary that implements the POVM [3]. Specifically, if \(U\) is a unitary that implements the POVM \(M\) to precision \(\epsilon\) such that, for all \(s\)-qubit density operators \(\rho\) we have

    \[\begin{equation} \left |\mathrm{Tr}(\rho M) -\mathrm{Tr}\left [U(\ket{0}\!\bra{0}^{\otimes a}\otimes\rho)U^\dagger (\ket{0}\!\bra{0}\otimes I_{a+s-1}))\right ] \right |\leq \epsilon, \end{equation}\]

    then \((I_1\otimes U^\dagger)(\mathrm{CNOT}\otimes I_{a+s-1})(I_1\otimes U)\) is a \((1,1+a,\epsilon)\)-block-encoding of \(M\) [1, Lemma 46]. - One can also implement a block-encoding of a Gram matrix using a pair of state-preparation unitaries \(U_L\) and \(U_R\). In particular, the product

    \[\begin{equation} U_A=U_L^\dagger U_R \end{equation}\]

    is a \((1,a,0)\)-block-encoding of the Gram matrix \(A\) whose entries are \(A_{ij}=\braket{\psi_i}{\phi_j}\), where [1, Lemma 47]

    \[\begin{equation} U_L\ket{0}^{\otimes a}\ket{i}=\ket{\psi_i},\qquad U_R\ket{0}^{\otimes a}\ket{j}=\ket{\phi_j}. \end{equation}\]
  • One can generalize the above strategy from Gram matrices to arbitrary matrices to produce \((\alpha, a, \epsilon)\)-block-encodings of general matrices \(A\), where again \(\alpha\geq\nrm{A}\). See Block-encoding classical data for details.
  • Sparse-access matrices: Given a matrix \(A\in\mathbb{C}^{2^w \times 2^w}\) that is \(s_r\)-row sparse and \(s_c\)-column sparse (meaning each row/column has at most \(s_r\) or \(s_c\) nonzero entries), then, defining \(\nrm{A}_{\mathrm{max}} = \max_{i,j} |A_{ij}|\), one can create a \((\sqrt{s_rs_c}\nrm{A}_{\mathrm{max}},w+3,\epsilon)\)-block-encoding of \(A\) using oracles \(O_r\), \(O_c\), and \(O_A\), defined below [1, Lemma 48]:
    \[\begin{align} & O_r:\ket{i}\ket{k}\mapsto \ket{i}\ket{r_{ik}}, & \forall i\in [2^w]-1, k\in [s_r] \\ & O_c:\ket{\ell}\ket{j}\mapsto \ket{c_{\ell j}}\ket{j}, & \forall \ell\in [s_c], j\in [2^w]-1 \\ & O_A:\ket{i}\ket{j}\ket{0}^{\otimes b}\mapsto \ket{i}\ket{j}\ket{A_{ij}}, & \forall i,j\in [2^w]-1 \end{align}\]

    In the above, \(r_{ij}\) is the index of the \(j\)-th nonzero entry in the \(i\)-th row of \(A\) (or \(j+2^w\) if there are less than \(i\) nonzero entries), and \(c_{ij}\) is the index of the \(i\)-th nonzero entry in the \(j\)-th column of \(A\) (or \(i+2^w\) if there are less than \(j\) nonzero entries), and \(\ket{A_{ij}}\) is a \(b\)-bit binary encoding of the matrix element \(A_{ij}\). To build the block-encoding, one needs one query to each of \(O_r\) and \(O_c\), and two queries of \(O_A\)—see [1, Lemma 48] and the more recent [4] for implementation details. If, in addition to being sparse, the matrix also enjoys some additional structure, e.g., there are only a few distinct values that the matrix elements can take, the complexity can be further improved, c.f. [5, 6]. Finally, note that the sparsity dependence can be essentially quadratically improved to \((\max(s_r.s_c))^{\frac{1}{2}+o(1)}\) using advanced Hamiltonian simulation techniques [7, Theorem 2] combined with taking the logarithm of unitaries [1, Corollary 71], however the resulting subroutine may be impractical and comes with a worse precision dependence. - For matrices given as a linear combination of unitary operators (LCU), we can block-encode the matrix using the LCU technique [8]. We provide a full description in the LCU section, and only give a brief outline here. For \(A = \sum_{i=1}^L c_i V_i\) with \(V_i\) unitary, we define the oracles \(\mathrm{PREPARE}\) (acting on \(\lceil \log_2(L)\rceil\) ancilla qubits) and \(\mathrm{SELECT}\) (acting on the ancilla and register qubits), and implement a \((\sum_i |c_i|, \lceil \log_2(L)\rceil, 0)\)-block-encoding of \(A\), using \(U := \mathrm{PREPARE}^\dag \cdot \mathrm{SELECT} \cdot \mathrm{PREPARE}\). The Hamiltonians of physical systems can often be written as a linear combination of a moderate number of Pauli operators, leading to a prevalence of this technique in quantum algorithms for chemistry [9, 10] and condensed matter physics [9, 11, 12].

In addition to the definition of block-encoding in \(\eqref{eq:BEDef}\), one can also define an asymmetric version as follows:

\[\begin{equation} \left\lVert A - \alpha (\bra{0}^{\otimes a} \otimes I )U_A(\ket{0}^{\otimes b} \otimes I)\right\rVert \leq \epsilon, \end{equation}\]

where \(a\) may not equal \(b\). In this case, \(U_A\) can be considered to be an \((\alpha, (a,b), \epsilon)\)- or an \((\alpha, \max(a,b), \epsilon)\)-block-encoding of \(A\). This can be useful for block-encoding a non-square matrix.

Dominant resource cost (gates/qubits)

The complexity of block-encoding an operator depends on the type of data or operator being encoded and any underlying assumptions. For instance, unitaries are naturally block-encodings of themselves, and hence their resource requirements depend entirely on their circuit-level implementation without any additional overhead for being a "block-encoding." By contrast, approaches that make use of state-preparation and QRAM to implement the block-encoding tend to have larger complexities, as those two subroutines typically dominate the resource requirements. For example, the best-known circuits that implement block-encoding matrices of classical data for general, dense \(N\times N\) matrices use \(\mathcal{O}\left( N\log(1/\epsilon) \right)\) qubits to achieve minimum \(T\)-gate count (which also scales as \(\mathcal{O}\left( N \log(1/\epsilon) \right)\)), or a larger \(\mathcal{O}\left( N^2 \right)\) number of qubits to achieve minimum \(T\)-gate depth (which scales as \(\mathcal{O}\left( \log(N)+\log(1/\epsilon) \right)\) [13]. In the sparse-access model, one can use \(\mathcal{O}\left( w+\log^{2.5}(s_rs_c/\epsilon) \right)\) one- and two-qubit gates, and \(\mathcal{O}\left( b+ \log^{2.5}(s_rs_c/\epsilon) \right)\) ancilla qubits [1], in addition to the calls to the matrix entry \(O_A\) and sparse access oracles \(O_r\) and \(O_c\), which must be implemented either by computing matrix entries "on-the-fly" or by using a QRAM primitive. Assuming appropriate binary representations of the numbers \(A_{ij}\), the exponents of the above logarithms can be reduced to \(1\) using the techniques of [4] (see also [9, Section III.D] and [14, Supplementary Material VII.A.2]).

The value of block-encodings is not that it is always cheap to implement them (as it depends on the relevant cost metric and the data access model); rather, the concept of block-encodings is powerful because it allows a practitioner of quantum algorithms to study and optimize the block-encoding construction independently of how it is used within the larger algorithm.

Caveats

A block-encoded matrix \(A\) must have norm \(\|A\|\leq 1\), or otherwise the matrix must first be normalized, and one must take care to keep track of normalization throughout the computation. In the definition of block-encodings shown above, the parameter \(\alpha\) plays the role of normalizing \(A\). Note that often the above constructions are suboptimal in the sense that \(\alpha\gg \|A\|\), which can lead to increased complexity.

For a given desired block-encoding, there can be several independent, yet equally valid implementations, and one can sometimes optimize for various resources when building the block-encoding. For example, many block-encoding strategies require a step in which some classical data is loaded into QRAM, but there are several ways of performing this data-loading step.

When using a block-encoding as part of a larger quantum algorithm, it is important to ensure that the overhead introduced by implementing a block-encoding will not outweigh any potential quantum speedups, as block-encoding can be very resource intensive.

The use of \(\ket{0}^{\otimes a}\) as the "signal" state is just one convention—we can use any "signal" state, given a unitary to prepare it [2]. One can also consider a more general definition known as "projected unitary encodings" which allows using an arbitrary subspace, rather than just a state-indexed block [1].

Example use cases

Block-encodings are ubiquitous in quantum algorithms, and they prevail in quantum algorithms that need coherent access to some linear operator or a method of implementing a non-unitary transformation on quantum data. Some specific examples:

Further reading

Reference [16] provides an instructive overview of the concept of block-encoding and showcases its power in several applications related to (generalized) regression problems. Meanwhile, [1] is a comprehensive collection of technical results about block-encodings and quantum linear algebra more generally.

Bibliography

  1. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 193–204. 2019. arXiv: https://arxiv.org/abs/1806.01838. doi:10.1145/3313276.3316366.

  2. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. arXiv: https://arxiv.org/abs/1610.06546. doi:10.22331/q-2019-07-12-163.

  3. Joran van Apeldoorn and András Gilyén. Improvements in quantum sdp-solving with applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 99:1–99:15. 2019. arXiv: https://arxiv.org/abs/1804.05058. doi:10.4230/LIPIcs.ICALP.2019.99.

  4. Yuval R. Sanders, Guang Hao Low, Artur Scherer, and Dominic W. Berry. Black-box quantum state preparation without arithmetic. Physical Review Letters, 122:020502, 1 2019. arXiv: https://arxiv.org/abs/1807.03206. URL: https://link.aps.org/doi/10.1103/PhysRevLett.122.020502, doi:10.1103/PhysRevLett.122.020502.

  5. Christoph Sünderhauf, Earl Campbell, and Joan Camps. Block-encoding structured matrices for data input in quantum computing. arXiv: https://arxiv.org/abs/2302.10949, 2023.

  6. Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. arXiv: https://arxiv.org/abs/2203.10236, 2023.

  7. Guang Hao Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 491–502. 2019. arXiv: https://arxiv.org/abs/1807.03967. doi:10.1145/3313276.3316386.

  8. Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12(11&12):901–924, 2012. arXiv: https://arxiv.org/abs/1202.5822. doi:10.26421/QIC12.11-12.

  9. Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X, 8(4):041015, 2018. arXiv: https://arxiv.org/abs/1805.03662. doi:10.1103/PhysRevX.8.041015.

  10. Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush. Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization. Quantum, 3:208, 12 2019. arXiv: https://arxiv.org/abs/1902.02134. URL: https://doi.org/10.22331/q-2019-12-02-208, doi:10.22331/q-2019-12-02-208.

  11. Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018. arXiv: https://arxiv.org/abs/1711.10980. doi:10.1073/pnas.1801723115.

  12. Kianna Wan. Exponentially faster implementations of select(h) for fermionic hamiltonians. Quantum, 2021. arXiv: https://arxiv.org/abs/2004.04170. doi:10.22331/q-2021-01-12-380.

  13. B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng. Quantum resources required to block-encode a matrix of classical data. IEEE Transactions on Quantum Engineering, 3:1–23, 2022. arXiv: https://arxiv.org/abs/2206.03505. doi:10.1109/TQE.2022.3231194.

  14. Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer. Quantum computing enhanced computational catalysis. Physical Review Research, 3(3):033055, 2021. arXiv: https://arxiv.org/abs/2007.14460. doi:10.1103/PhysRevResearch.3.033055.

  15. Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009. arXiv: https://arxiv.org/abs/0811.3171. doi:10.1103/PhysRevLett.103.150502.

  16. Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The power of block-encoded matrix powers: improved regression techniques via faster hamiltonian simulation. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), 33:1–33:14. 2019. arXiv: https://arxiv.org/abs/1804.01973. doi:10.4230/LIPIcs.ICALP.2019.33.

  17. Alexander M Dalzell, B David Clader, Grant Salton, Mario Berta, Cedric Yen-Yu Lin, David A Bader, Nikitas Stamatopoulos, Martin J A Schuetz, Fernando G S L Brandão, Helmut G Katzgraber, and others. End-to-end resource analysis for quantum interior point methods and portfolio optimization. PRX Quantum, pages to appear, 2023. arXiv: https://arxiv.org/abs/2211.12489.

  1. References to locations in [1] typically refer to the longer arXiv version, rather than the STOC version. ↩