{'fraction_non_alphanumeric': 0.031378701706216906, 'fraction_numerical': 0.0092828659214225, 'mean_word_length': 4.392139584067677, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
FABLE: Fast Approximate Quantum Circuits for Block-Encodings

Block-encodings of matrices have become an essential element of quantum algorithms derived from the quantum singular value transformation. This includes a variety of algorithms ranging from the quantum linear systems problem to quantum walk, Hamiltonian simulation, and quantum machine learning. Many of these algorithms achieve optimal complexity in terms of black box matrix oracle queries, but so far the problem of computing quantum circuit implementations for block-encodings of matrices has been under-appreciated. In this paper we propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner. FABLE circuits have a simple structure and are directly formulated in terms of one- and two-qubit gates. For small and structured matrices they are feasible in the NISQ era, and the circuit parameters can be easily generated for problems up to fifteen qubits. Furthermore, we show that FABLE circuits can be compressed and sparsified. We provide a compression theorem that relates the compression threshold to the error on the block-encoding. We benchmark our method for Heisenberg and Hubbard Hamiltonians, and Laplacian operators to illustrate that they can be implemented with a reduced gate complexity without approximation error.

Block-encodings of matrices have become an essential element of quantum algorithms derived from the quantum singular value transformation. This includes a variety of algorithms ranging from the quantum linear systems problem to quantum walk, Hamiltonian simulation, and quantum machine learning. Many of these algorithms achieve optimal complexity in terms of black box matrix oracle queries, but so far the problem of computing quantum circuit implementations for block-encodings of matrices has been under-appreciated. In this paper we propose FABLE, a method to generate approximate quantum circuits for block-encodings of matrices in a fast manner. FABLE circuits have a simple structure and are directly formulated in terms of one-and two-qubit gates. For small and structured matrices they are feasible in the NISQ era, and the circuit parameters can be easily generated for problems up to fifteen qubits. Furthermore, we show that FABLE circuits can be compressed and sparsified. We provide a compression theorem that relates the compression threshold to the error on the block-encoding. We benchmark our method for Heisenberg and Hubbard Hamiltonians, and Laplacian operators to illustrate that they can be implemented with a reduced gate complexity without approximation error.

I. INTRODUCTION
The quantum singular value transformation (QSVT) [1,2] combines and extends qubitization [3] and quantum signal processing [4]. The QSVT provides a unifying framework encompassing many quantum algorithms that provide a speed-up over the best known classical algorithm [5]. All quantum algorithms derived from the quantum singular value transformation ultimately rely on the notion of a block-encoding of some matrix A that represents the problem at hand. This matrix can, for example, be the Hamiltonian of the quantum system to be simulated [6], the discriminant matrix of the Markov chain in a quantum walk [7,8], or the matrix to be solved for in the quantum linear systems problem [9]. These matrices are, in general, non-unitary operators and cannot be directly run on a quantum computer that only performs unitary evolution. This constraint is usually overcome by enlarging the Hilbert space and embedding the non-unitary operator in a specific state of the ancillary qubits. The most commonly used embedding is a block-encoding where the system matrix A is embedded in the leading principal block of a larger unitary matrix acting on the full Hilbert space: where * indicate arbitrary matrix elements. We assume that A 2 ≤ 1 since otherwise such an embedding cannot exist. In this case, we say that U block encodes A.
Thus far, complexity results for quantum algorithms derived from the quantum singular value transformation have been formulated in terms of query complexity, i.e., how many queries to the block-encoding U are required to solve the problem. The question how a quantum circuit can be generated for Eq. (1) has so far been under appreciated. Encoding schemes for sparse matrices have been proposed [1,9] and ultimately rely on sparse access oracles for which a quantum circuit implementation can be challenging. Some explicit circuit implementations for quantum walks on highly-structured graphs are provided in [10] and are closely connected to block-encodings [1].
Similarly, [11] shows how to generate quantum circuits for block-encoding certain specific 2 n × 2 n sparse matrices in poly(n) complexity.
In this paper we take a more general approach and propose FABLE, which stands for Fast Approximate BLock-Encodings. FABLE is an efficient algorithm to generate quantum circuits that block encode arbitrary matrices up to prescribed accuracy. FABLE circuits consist of a matrix query oracle, that we implement with simple onequbit R y and R z rotations and two-qubit CNOT gates, and some additional Hadamard and SWAP gates. The gate complexity of a FABLE circuit for general, unstructured N × N matrices is bounded by O(N 2 ) gates with a modest prefactor of 2 for real-valued matrices (4 for complex-valued matrices), and a limited polylogarithmic overhead. In this sense, FABLE circuits are a quantum circuit representation of dense matrices with an optimal asymptotic gate complexity. However, this gate complexity scales exponentially in the number of qubits for generic dense matrices as encoding an unstructured matrix of exponential dimension is a difficult task. Luckily, more relevant problems usually contain a lot of structure and, as we will show, FABLE circuits can be com-pressed which often leads to significantly reduced gate complexities for many problems of interest. This process can be interpreted as a sparsification of the circuit and matrix. However, the FABLE algorithm applies a Walsh-Hadamard transformation to the matrix data and performs the sparsification in the Walsh-Hadamard domain. Sparse FABLE matrices thus corresponds to matrices that contain many zeros in this domain, which does not necessarily correspond to sparsity in the original domain. Thanks to these characteristics, FABLE circuits are well-suited for implementing quantum algorithms derived from the QSVT in the NISQ era and beyond.
The remainder of this paper is organized as follows. Section II formally defines the concept of blockencodings. Section III presents a circuit structure for block-encodings in terms of a matrix query oracle and gives a naive implementation of this oracle. Section IV introduces the improved circuit implementation for matrix query oracles that are used in FABLE circuits for realand complex-valued matrix data. In Section V, we extended the definition of block-encodings to approximate block-encodings and we discuss how FABLE circuits can be compressed. We relate the threshold in the compression algorithm to the error on the block-encoding. Section VI provides some examples that show that FABLE can be used to block encode Heisenberg and Hubbard Hamiltonians and discretized differential operators with a significantly reduced gate complexity.
Implementations of the FABLE algorithm built on top of QCLAB [12,13] and Qiskit [14] are made publicly available on https://github.com/ QuantumComputingLab/fable. Without loss of generality, we assume in the remainder of this paper that the matrix size is N × N with N = 2 n .

II. BLOCK-ENCODINGS
A block-encoding of a non-unitary matrix is the embedding of a properly scaled version of that matrix in the leading principal block of a bigger unitary [1,2]. A formal definition for a block-encoding of an n-qubit matrix A in an m-qubit unitary U is as follows.
Definition 1. Let a, n, m ∈ N, m = a + n. Then an mqubit unitary U is a (α, a)-block-encoding of an n-qubit and A = αÃ.
The parameters (α, a) are, respectively, the subnormalization factor necessary for encoding matrices of arbitrary norm and the number of ancilla qubits used in the block-encoding. Since U 2 = 1, we have that Ã 2 ≤ 1 and therefore A 2 ≤ α. Every unitary is already a trivial (1, 0)-block-encoding of itself and every non-unitary matrix can be embedded in a ( A 2 , 1)block-encoding [15]. This does not guarantee the existence of an efficient quantum circuit implementation, but merely considers the matrix representation. For a block-encoding, we say thatÃ is the partial trace of U over the zero state of the ancilla space. This naturally partitions the Hilbert space H m into H a ⊗ H n . Given an n qubit state, |ψ ∈ H n , the action of U on |φ = |0 ⊗a ⊗ |ψ becomes with and |σ ⊥ the normalized state for which the ancilla register has a state orthogonal to |0 ⊗a . With probability Ã |ψ 2 , a partial measurement of the ancilla qubits results in 0 ⊗a and the signal qubits are in the target statẽ A |ψ / Ã |ψ . Using amplitude amplification [2,16], this process must be repeated 1/ Ã |ψ times for success on average.   1 provides the high-level structure of a quantum circuit for a block-encoding. We note that an encoding of a matrix can be coupled to any other state of the ancilla space besides the all-zero state and this state does not even have to be a computational basis state. This generalization is discussed in [1]. Encoding the matrix data in the all-zero state of the ancilla qubits has become the most widely used choice as this leads to an embedding of the matrix in the leading block of the unitary matrix, i.e., a block-encoding.

III. QUANTUM CIRCUITS FOR BLOCK-ENCODINGS
Quantum circuits for block-encodings of sparse matrices are often presented in terms of query oracles that provide information about the position and binary description of the matrix entries [2,9]. These oracles can be combined into a matrix query oracle [17] that provides access to the matrix data.
Our approach is different, we immediately define a matrix query operation O A for a given matrix A and consequently discuss how this oracle can be directly synthesized in a quantum circuit.
where |i and |j are n-qubit computational basis states.
A high-level quantum circuit to block-encode a matrix A is proposed in Fig. 2, where H ⊗n is an n-qubit Hadamard transformation that creates an equal superposition over the row qubits, the matrix query unitary O A is given in (6), and the 2n-qubit SWAP gate is implemented as SWAP |i |j = |j |i . This circuit is closely related to similar circuits in [17], but we encode all information about the matrix in a single matrix query oracle.
High-level quantum circuit structure for blockencoding a matrix A in terms of a matrix query oracle OA. If the n + 1 ancilla qubits are measured in the zero state, the signal register is in the desired stateÃ |ψ / Ã |ψ .
The following theorem ascertains that the circuit from Fig. 2 is indeed a block-encoding of the target matrix A. Our proof follows a similar reasoning to [17] and is included for completeness.
Proof. The circuit U A can be written in matrix notation as: For U A to be an (1/2 n , n + 1)-block-encoding of A, we need to verify according to Definition 1 that On one hand, we have while on the other hand, we have Combining both, yields which completes the proof.
All circuit elements in Fig. 2, except for O A , can be readily written in simple 1-and 2-qubit gates. The complexity of the Hadamard and SWAP gates is only poly(n). We present next how the oracle O A from Definition 2 can be implemented in simple 1-and 2-qubit gates for arbitrary matrices. We first consider the cases of real-valued matrices and discuss complex-valued matrices in Section IV B.
In case that A is a real-valued matrix, we see from (6) that for given row and column indices i and j, O A acts on the |0 state of the first qubit as an R y gate with angle i.e., Hence, the matrix query unitary O A is a matrix with the following structure for real-valued matrices where c ij := cos(θ ij ) and s ij := sin(θ ij ), with θ ij given by (7).
A first naive implementation of the O A oracle (6) for A ∈ R N ×N uses N 2 multi-controlled R y gates. We use the notation C n (R y ) for an R y gate with n control qubits. The circuit construction for O A uses one C n (R y ) gate for each matrix entry a ij where the control qubits encode the row and column indices |i |j of the corresponding entry. This circuit is illustrated below for the encoding of a 2×2 matrix using 3 qubits and 4 C 2 (R y ) gates where θ 00 , θ 01 , θ 10 , θ 11 are given by (7). It is clear that this circuit implements (6) for real-valued data. The major disadvantage of this naive approach is that it re- However, every C 2n (R y ) requires O(N 2 ) 1and 2-qubit gates to be implemented [18]. This brings the total gate complexity of this naive circuit implementation to O(N 4 ) which is excessive as it is quadratically worse than the classical representation cost. We propose a quadratic reduction in gate complexity with the FABLE implementation of block-encoding circuits in the next section.

IV. FABLE CIRCUITS FOR BLOCK-ENCODINGS
We continue with the case of real-valued matrices and discuss how to extend this to complex-valued matrices afterwards.

A. Query oracles for real-valued matrices
We illustrate the idea of the improved circuit construction for O A for a small-scale example of A ∈ R 2×2 from the previous section. In that case, the circuit structure is given by where the anglesθ 0 ,θ 1 ,θ 2 ,θ 3 are computed from the data A ∈ R 2×2 as we will explain next. The circuit structure is derived from [19]. We analyze the action of the above circuit based on the following two elementary properties of R y rotations: It follows that the state of the first qubit is rotated as 00 : where the rotation angle depends on the state of the last two control qubits as indicated above. To implement an O A oracle with angles θ 00 , θ 01 , θ 10 , θ 11 as given by (7), we vectorize A to vec(A) in row-major order such that vec(A) i+j·N = a ij to obtain relabeled angles (θ 0 , . . . , θ 3 ). We see from the system of equation above that these angles have to satisfy This is a structured linear system that can be written as whereĤ = 1 1 1 −1 is a scalar multiple of the Hadamard gate and P G is the permutation matrix that transforms binary ordering to Gray code ordering.
This algorithm generalizes to O A oracles for matrices A ∈ R N ×N [19]. The corresponding circuit structure consists of a gate sequence of length 2 2n alternating between R y and CNOT gates. Note that the R y gates only act on the first qubit, which is also the target qubit of the CNOT gates, and the control qubit for the th CNOT gate is determined by the bit where the th and ( +1)st Gray code differ. For an O A oracle with angles θ = (θ 0 , . . . , θ 2 2n −1 ) given by (7), the angles of the R y gates in the quantum circuit,θ = (θ 0 , . . . ,θ 2 2n −1 ), are related to θ through the linear system This linear system can be efficiently solved by a classical algorithm in O(N 2 log N 2 ) using a fast Walsh-Hadamard transform [20] which is implemented in the reference implementation of FABLE. This circuit structure is known as a uniformaly controlled R y rotation [19] because it rotates the target qubit over a different angle for each bitstring in the control register. We use the following concise notation for uniformly controlled rotations used in the implementation of O A : The gate complexity of implementing O A with this approach is O(N 2 ) for A ∈ R N ×N , where N 2 CNOT and N 2 single-qubit R y gates are required, i.e., the prefactor in the circuit complexity is 2. This reaches the same asymptotic gate complexity as classically required to store the data and is optimal for unstructured data.

B. Query oracles for complex-valued matrices
In case that A is a complex-valued matrix, we encode the matrix elements as a product of R y and R z rotations. For given row and column indices i and j, the matrix element to be encoded is a ij = |a ij |e ıαij , and O A acts on the |0 state of the first qubit as a product of an R y and R z gate with angles i.e., Our previous analysis extends to uniformly controlled R z rotations because the conditions in (10) are satisfied for R z gates [19]. It follows that we can implement the O A oracle for complex-valued matrices as the product of uniformly controlled R y and R z rotations where the R y and R z rotations respectively set the magnitude and phase of the matrix elements. The corresponding rotation angles can be computed separately through two independent linear systems of the form (14) by using the magnitude and phase of the matrix data, respectively. Hence, the gate complexity for O A oracles of complex-valued matrices is twice the cost of real-valued matrices, while the asymptotic complexity in terms of 1and 2-qubit gates remains O(N 2 ).
The complete FABLE circuits for the real and complex case with the O A oracles implemented as uniformly controlled rotations are given in Fig. 3.

|0
Ry(θ) 0 3. FABLE quantum circuit structures for real and complex matrices with OA oracles implemented as uniformly controlled rotations.

V. APPROXIMATE BLOCK-ENCODINGS AND CIRCUIT COMPRESSION
Thus far we have only considered exact implementations of O A resulting in exact block-encodings. In this section, we focus the "A" in FABLE and introduce approximate block-encodings. We show how to compress FABLE circuits and what the resulting approximation error of the block-encoding is.

A. Approximate block-encodings
We begin with extending Definition 1 to approximate block-encodings that only implement the target matrix up to a certain precision ε.
Definition 3. Let a, n, m ∈ N, m = a + n, and ε ∈ R + . Then an m-qubit unitary U is an (α, a, ε)-block-encoding of an n-qubit operator A if and A − αÃ 2 ≤ ε.
The parameter ε is the absolute error on the blockencoding. As before, we have that Ã 2 ≤ 1 and therefore A 2 ≤ α + ε.

B. FABLE circuit compression and sparsification
We illustrate the idea of the circuit compression algorithm for a uniformly controlled rotation gate with 8 angles: For conciseness, we have omitted the labels from the rotation gates and only show their parameter. The gates can be R y , R z , or in general R α gates with α a normalized linear combination of σ y and σ z because the conditions in (10) are satisfied for all R α gates [19]. The compression algorithm uses a cutoff threshold δ c ∈ R + and considers allθ i ≤ δ c to be negligible. Assume for the example above thatθ 2 ,θ 3 ,θ 4 ,θ 5 ,θ 6 ≤ δ c . This means that the respective single-qubit rotations can be removed from the circuit, yieldinĝ The resulting circuit contains a series of consecutive CNOT gates that can be further simplified as they mutually commute and share the same target qubit. Any two CNOT gates in a series of consecutive CNOT gates that have the same control qubit cancel out. It follows that in the example circuit, 5 single qubit rotations and 4 CNOT gates can be removed, yielding the compressed circuit:θ The circuit compression algorithm consists of two steps: i. Remove all rotation gates for anglesθ i ≤ δ c inθ from the circuit; ii. Perform a parity check on the control qubits of the CNOT gates in each series of consecutive CNOT gates: keep one CNOT gate with control qubit i if there are an odd number of CNOT gates with control qubit i in the series, otherwise remove all CNOT gates with control qubit i.
This procedure can be considered as data sparsification since it allows us to represent the block-encoded matrix with fewer than N 2 parameters. However, since we perform the sparsification on theθ angles after the Walsh-Hadamard transform, a sparse representation ofθ does not typically mean that θ and A are sparse in the usual sense of containing many zeroes. FABLE circuits are efficient for the class of matrices that are sparse in the Walsh-Hadamard domain.
The following theorem relates the cutoff threshold δ c used in the circuit compression algorithm to the firstorder error on the block-encoding as defined in Definition 3. We consider the case of real-valued data.
Theorem 2. For an n-qubit matrix A ∈ R N ×N , |a ij | ≤ 1, the FABLE circuit with cutoff compression threshold δ c ∈ R + gives an (1/2 n , n + 1, N 3 δ c )-block-encoding of A up to third order in δ c .
Proof. In order to prove that a cutoff compression threshold δ c leads to an absolute error of at most N 3 δ c + O(δ 3 c ) on the the block-encoding, we start with the linear system (14) that relates the angles of the uniformly controlled rotationsθ to the angles of the matrix query oracle θ.
By linearity, the error on O A thus becomes δθ =θ − θ = (Ĥ ⊗2n P G )δθ, and we get that as P G is a unitary matrix and Ĥ ⊗2n 2 = N . This implies that the element-wise error is now only bounded by |δθ i | = |θ i −θ i | ≤ N 2 δ c . This relates to the element-wise error on a i as: In the final approximation, we used a truncated series expansion. We thus have that δa 2 ≤ N 3 δ c . As A 2 ≤ A F = vec(A) 2 we get the upper bound.
Numerical results that verify this error bound are presented in Fig. 4 which shows the result of noise-free QCLAB [12] simulations for compressed FABLE circuits. The FABLE circuits are generated for randomly generated matrices with entries drawn from the standard normal distribution, the matrices are 2 to 7 qubit operators such that the FABLE circuits require 5 to 15 qubits. We observe that the bound from Theorem 2 always holds but is overly pessimistic. Not shown in Fig. 4 are the majority of random realizations with an error close to the 10 −16 machine precision. A similar analysis can be performed for the complexvalued case where the error on the magnitude and phase of the matrix data have to be considered independently.

VI. DISCUSSION AND EXAMPLES
FABLE circuits provide a fast and convenient way of generating quantum circuits consisting of simple 1and 2-qubit gates that block-encode arbitrary matrices. Thanks to their versatility, we expect them to become very useful to run and benchmark quantum algorithms derived from the QSVT for small to medium-scale experiments in the NISQ era.
The conditions imposed on the block-encoded matrix are minimal: a FABLE circuit exists for any matrix that satisfies |a ij | ≤ 1 as this is the only requirement for real rotation angles to exist according to (7) and (15). For matrices of small norm, the probability of a successful measurement can vanish. In the extreme case of the allzero matrix, a FABLE encoding exists, but the probability of measuring the desired state will also be zero.
For the remainder of this section, we show the gate complexities of FABLE circuits for three different model problems: a Heisenberg Hamiltonian, a Fermi-Hubbard Hamiltonian in 1D and 2D, and a discretized Laplacian operator in 1D and 2D. We have selected these example problems as they perform well within FABLE encodings and require relatively few gates. However, we do indicate that for more complicated model problems this is not necessarily the case, which highlights the limitations of our approach.

A. Heisenberg Hamiltonians
Block-encodings of Hamiltonians are of particular interest as they can be used in the QSVT for Hamiltonian simulation [1] or for preparing ground and excited states [21]. Where previous theoretical analysis showed that these methods have optimal asymptotic scaling in terms of oracle query complexity, we can now directly use FABLE to obtain an upper bound for the asymptotic gate complexity for specific Hamiltonians.
We study the performance of FABLE for blockencoding localized Hamiltonians. Specifically, we are interested in Heisenberg type spin chains Hamiltonians where X (i) , Y (i) , and Z (i) are the Pauli matrices, acting on the ith qubit. We consider a Heisenberg XXX model where J x = J y = J z , h z = 0 for systems of 2, . . . , 7 qubits. We set the compression threshold δ c to m , with m the machine precision . The CNOT and R y gate complexities are summarized in Fig. 5. We observe that even with such a small compression threshold, FABLE can give an accurate encoding of a Heisenberg XXX model with just 50% of the CNOT gates and 25% of the R y rotations.
More general Heisenberg models with different values for J x , J y and J z or with an external field (h z = 0) can be encoded with FABLE, but their circuits cannot be compressed and sparsified even though the corresponding matrices are sparse.

B. Fermi-Hubbard model
The second example we consider is a special case of the Fermi-Hubbard Hamiltonian, where c † iσ (c iσ ) is the creation (annihilation) operator for site i and spin σ. The first term is the hopping term with strength t, the second term is the interaction term with strength U . We generate the Hamiltonian through OpenFermion [22] for the case t = 1, U = 0, i.e., non-interacting fermions on a 1D and 2D lattices with two spin orbitals per site and non-periodic boundary conditions. The resulting Hamiltonians are mapped to qubits using the Bravyi-Kitaev transformation and block-encoded with FABLE. The compression threshold is again set to m and the gate complexities of the FABLE circuits are listed in Table I. We observe that both in 1D and 2D the operators can be encoded with a relatively small fraction of the maximum number of gates and that this fraction decreases for growing problem size. We ran the same experiment for interacting Hubbard Hamiltonians (U = 0) but for this case, the matrices do not compress well and the maximum number of gates is required to encode the Hamiltonians.
C. Elliptic partial differential equations As a second example we consider 1D and 2D discretized Laplace operators which are relevant in the solution of elliptic partial differential equations such as the Laplace equation ∆u = 0 and the Poisson equation ∆u = f . We consider finite difference discretization of the second order derivatives. For example, on a 1D equidistant grid with Dirichlet boundary conditions, we approximate the second order derivate in point x j as: where ∆x is the step size. This three-point stencil leads to the 1D discretized Laplace operator: where the entries * in the lower-left and upper-right corner are either both equal to 0 for non-periodic boundary conditions, or both equal to −1 for periodic boundary conditions. In 2D, the discretized Laplace operator becomes the Kronecker sum of discretizations along the x-and ydirections: which corresponds to a five-point stencil. This allows for periodic or non-periodic boundary conditions and the number of discretization points can differ in both dimensions. Second order derivatives are of great importance in quantum field theory [23] and can be useful to simulate scalar fields with quantum computers. We generate 1D Laplacian matrices (22) on 2 to 7 qubits and use FABLE to generate block-encoding circuits. The compression threshold is set to m such that an accurate block-encoding is obtained. The results are summarized on the first row of Fig. 6 for non-periodic and periodic Dirichlet boundary conditions. Similarly, the second row of Fig. 6 shows the results of encoding 2D Laplacians on different rectangular grids requiring at most 7 qubits.
The following pertinent observations can be made from these results. First, periodic boundary conditions lead to much reduced gate counts compared to non-periodic boundary conditions. This is natural as there exist more structure in the periodic Laplacians. Second, the 2D Laplacians can be compressed better than 1D Laplacians and require in some cases fewer than 5% of the maximum number of gates. Third, for the 2D Laplacians, discretization grids with a smaller aspect ratio, i.e., closer to a square, require in general fewer gates than more rectangular grids for the same number of grid points.

D. Quantum image encodings
The circuit construction in FABLE is based on the concept of uniformly controlled rotations introduced in [19]. This circuit construction method was recently used in the QPIXL framework that unifies quantum image representations [24]. In all proposed quantum image representations and quantum image processing algorithms, the image is encoded in a quantum state and the circuit implementation becomes a state preparation problem. FABLE, and block-encodings in general, can be directly  used to encode image data by embedding it in the unitary operator itself. This alternative to previously proposed quantum image encodings could potentially have benefits for certain quantum image processing tasks as it trivially preserves the 2D structure in the image.

VII. CONCLUSION
In this paper, we have introduced FABLE, an algorithm for fast generation of quantum circuits that approximately block-encode arbitrary target matrices. FA-BLE circuits obtain the optimal asymptotic gate complexity for generic dense operators and can be efficiently compressed for many problems of interest. Circuit compression and sparsification can lead to a significant reduction in gate complexity. More specifically, matrices that are sparse in the Walsh-Hadamard domain can in general be efficiently encoded. An interesting future research direction would be to precisely characterize the class of matrices that are sparse in the Walsh-Hadamard domain as these have great potential for successful experimental realizations of quantum algorithms based on block-encodings.
We analyzed the relation between the compression threshold and the approximation error in the blockencoding and provide an upper bound on this error in Theorem 2 which shows a linear relation between the compression threshold, the problem size, and the approximation error. Our numerical simulations show that this bound can be saturated for larger thresholds and problem sizes.
We illustrated FABLE on example problems ranging from Heisenberg and Hubbard Hamiltonians to discretized Laplacian operators. These examples show that high compression levels are feasible for certain structured problems, but we have observed that more general Hamil-tonians with more interaction terms do not compress well. This highlights the limitation of our direct approach to encoding the matrix data. Balancing direct FABLE encodings of smaller terms in the Hamiltonian expression with a Linear Combination of Unitaries (LCU) [25] circuit construction in order to combine the smaller terms into a large-scale block-encoding can potentially mitigate this issue. This is another future research direction.