We introduce an efficient classical-quantum algorithm for encoding arbitrary dense Hermitian matrices as Block Encoding circuits (\(\matU _{\matA }\in \BE {\matA }{\alpha ,\theta }\)). Our work is motivated by Block Encoding’s fundamental role as the leading paradigm for quantum linear algebra, providing a unified framework for leveraging quantum computing to accelerate numerical linear algebra operations. Our algorithms, accepts four distinct input representations: (1) classical matrix description \(\matA \in \C ^{n\times n}\), (2) an \(4\times 4\times \cdots \times 4\) (\(\log n\) times) Pauli coefficients tensor \(\matA _{P}\), (3) matrix state preparation circuit \(\cirU _{\matA }\), or (4) matrix state preparation circuit for the Pauli tensor \(\cirU _{\matA _{P}}\). This flexibility optimizes performance across different data availability scenarios, with the classical matrix input achieving \(O(n^{2}\log n)\) run-time complexity in the worst case. Moreover, the third input model demonstrates a significant breakthrough: the first known method to construct a Block Encoding circuit directly from a matrix state preparation circuit without requiring additional classical information (such as row norms) or additional quantum hardware (such as QRAM). This establishes a new bidirectional equivalence between block encoding and matrix state preparation input models, providing a unified framework for matrix encoding in quantum algorithms.

1 Introduction

1.1 Motivation and problem statement

Quantum computers hold hope for significant speedups in scientific computing and machine learning due to their ability to handle matrix operations efficiently [3]. However, unlocking this potential hinges the algorithm’s ability to efficiently access classical data within the quantum system. The mechanism in which classical input is fed into a quantum algorithm is known as the algorithm’s input model.

Leveraging breakthroughs in quantum linear algebra, researchers have proposed many quantum algorithms for scientific computing and machine learning. However, the feasibility of their input model assumptions remains critical to their effectiveness. As shown by Chakraborty et al. [4], these assumptions often significantly impact the performance and efficiency of such algorithms. Prime examples of quantum linear algebra algorithms include the HHL algorithm [8], and others [5, 7, 14, 2, 11].

Given the essential role of the input model in defining how classical data interacts with the quantum system, researchers have explored various approaches. Two noteworthy examples include the sparse-data access model [1, 5] and various quantum data structure based models [9, 10].

In this work, we study the use of Pauli decomposition in developing efficient algorithms to encode arbitrary dense or sparse Hermitian matrices into Block Encoding circuits, either provided as classical data or as quantum circuits, into Block Encoding circuits.

1.2 Brief overview of Block Encoding and State preparation

Chakraborty et al. [4] showed that a variety of the aforementioned widely used input models can be reduced to an input model in which matrices are inputed using block encodings and vectors are inputed as state preparation circuits:

We refer to the input model in which matrices are accessed using block encodings and vectors are accessed as state preparation circuits as the block encoding input model. There are powerful algorithms that operate under the block encoding model. In particular, in the block encoding model we can perform Quantum Singular Value Transformation [7], a powerful technique that leads to efficient algorithms for solving linear equations, amplitude amplification, quantum simulation, and more [12].

Another relevant input model is the state preparation input model. In this model, matrices accessed via matrix state preparation circuit and vectors are accessed via state preparation circuits. Mor-Yosef et al. [15] recently introduced an algorithm for multivariate trace estimation and spectral sums estimation under this model.

1.3 Statement of main results

While existing block encoding methods typically exploit specific matrix properties like structure, sparsity, or rank, we introduces an efficient general-purpose technique for arbitrary matrices (dense and sparse) through Pauli decomposition. These techniques will utilize the principles of Pauli decomposition, and the use of a quantum multiplexer.

The Pauli decomposition represents matrices as a sum of tensor products of Pauli matrices. Formally, let \(\Sigma =\{\matI =0,\matX =1,\matY =2,\matZ =3\}\) represent a set of indices corresponding to the four \(2\times 2\) Pauli matrices: \(\sigma _{I},\sigma _{X},\sigma _{Y},\sigma _{Z}\). Assume that \(n=2^{q}\). Given a word (i.e., sequence) \(\calW =(w_{1},w_{2},\dots ,w_{q})\in \Sigma ^{q}\), we define the corresponding \(q\)-wise Pauli matrix as \(\sigma _{\calW }\coloneqq \sigma _{w_{1}}\otimes \sigma _{w_{2}}\otimes \cdots \otimes \sigma _{w_{q}}\). Then, the Pauli decomposition of matrix \(\matA \) can be expressed mathematically as:

\[ \matA =\sum _{\calW \in \Sigma ^{q}}\alpha _{{\cal W}}\sigma _{{\cal W}} \]

where \(\alpha _{\calW }\in \R \) are real coefficients.

The quantum multiplexer [13] acts like a switch within a quantum circuit. It uses control qubits to selectively apply different unitary operations to a target qubit. Given a set of quantum circuits \({\cal U}_{0},\dots ,{\cal U}_{k-1}\) the \(\log k\)-qubit multiplexer is defined as:

\[ {\cal MX}_{\log k}\coloneqq \sum _{i=0}^{k-1}\Ket i\Bra i\otimes {\cal U}_{i}. \]

Importantly, \({\cal MX}_{\log k}\) acts as a multiplexer. In other words:

\[ {\cal MX}_{\log k}(\underbrace {\Ket i}_{control}\underbrace {\Ket {\psi }}_{input})=\underbrace {\Ket i}_{control}\underbrace {{\cal U}_{i}\Ket {\psi }}_{output}. \]

The matrix that represents the multiplexer is a block diagonal matrix of the corresponding operators:

\[ \matM ({\cal MX}_{\log k})=\diag {\matM ({\cal U}_{0}),\ldots ,\matM ({\cal U}_{k-1})} \]

Once we have obtained the Pauli coefficients of the matrix, we can utilize a multiplexer to construct a block-diagonal matrix composed of the corresponding q-wise Pauli matrices. By employing a state preparation circuit for the coefficients, we can efficiently implement linear combinations of coefficients multiplied by matrices, effectively creating a block encoding of the matrix \(\matA \).

To efficiently determine the Pauli coefficients classically, we require some theoretical groundwork.

1.4 Contribution

This work makes three key contributions: (a) the first bidirectional equivalence between block encoding and matrix state preparation input models, (b) a novel classical Pauli decomposition algorithm with \(O(n^{2}\log n)\) run-time complexity, and (c) an efficient quantum circuit implementation for multiplexed Pauli tensor products with \(O(n^{2})\) gate complexity. This general-purpose approach improves upon existing techniques for arbitrary matrix encoding, achieving particular efficiency when the Pauli decomposition is sparse.

2 Block encoding equivalence

Given a matrix state preparation circuit for \(\matA \) and a state preparation circuit for a vector \(\w \) whose entries are the row norms of \(\matA \), it is possible to construct a block encoding of \(\matA \) [6, Section I.D]. We are unaware of any efficient algorithm that given only a matrix state preparation circuit for \(\matA \) constructs a block encoding of \(\matA \). In this section we will show a way to create block encoding from state preparation circuits and vise versa.

2.1 Block encoding \(\to \) matrix state preparation circuit

Mor-Yosef et al. [15] show that given a circuit \(\cal U\) we can construct a matrix state preparation of \(\matM ({\cal U})\). Thus, given a block encoding of \(\matA \) we can immediately construct a matrix state preparation circuit for a matrix that contains \(\matA \).

The following provides a proof for creating a state preparation circuit, including auxiliary (garbage) quantum states, from Block Encoding.

2.2 Matrix state preparation circuit \(\to \) block encoding

We introduce a method to create block encoding solely from a matrix state preparation circuit. Preliminary examples are provided to illustrate this approach, with the full methodology detailed in the paper. At a high level, we construct \({\cal U}_{\matA _{p}}\) from \({\cal U}_{\matA }\), and then apply the technique from the previous section to block encode \(\matA \).

In high level, we construct \({\cal U}_{\matA _{p}}\) from \({\cal U}_{\matA }\), then use the technique from the previous section to block encode \(\matA \). We will now demonstrate how to compute \({\cal U}_{\matA _{p}}\) in the following section.

2.2.1 Construct \({\cal U}_{\protect \matA _{p}}\) from \({\cal U}_{\protect \matA }\)( Warm-up: \(q=1\) and Real \(\protect \matA \))

As a warm-up, let us first consider the case of \(q=1\), i.e. the \(\matA \in \R ^{n\times n}\) a \(2\) by \(2\) real and Hermitian matrices. To keep notation simple, we use the 1 base index, i.e.

\[ \matA =\left [\begin {array}{cc} a_{11} & a_{12}\\ a_{21} & a_{22} \end {array}\right ]\,\,\,\,a_{12}=a_{21} \]

Note that we can write \(\matA \) as a linear combination of the following matrices,

\[ \matE _{11}=\left [\begin {array}{cc} 1 & 0\\ 0 & 0 \end {array}\right ],\,\matE _{12}=\left [\begin {array}{cc} 0 & 1\\ 0 & 0 \end {array}\right ],\,\matE _{21}=\left [\begin {array}{cc} 0 & 0\\ 1 & 0 \end {array}\right ],\,\matE _{22}=\left [\begin {array}{cc} 0 & 0\\ 0 & 1 \end {array}\right ] \]

Indeed we have that

\[ \matA =\sum _{i,j}a_{ij}\matE _{i,j}=a_{11}\matE _{11}+a_{12}\matE _{12}+a_{21}\matE _{21}+a_{22}\matE _{22} \]

From linearity of \(\left (\cdot \right )_{p}\)we have that

\[ \matA _{p}=\left (\sum _{i,j}a_{ij}\matE _{ij}\right )_{p}=\matA =\sum _{i,j}a_{ij}\left (\matE _{ij}\right )_{p} \]

Note that we can create state preparation circuits \(\{{\cal U}_{\left (\matE _{ij}\right )_{p}}\}_{i,j}\), using the standard state prepartion operation ([13]). Now we can create the \({\cal U}_{\matA _{p}}\) as follow:

This observation can easily be used to implement, via qMSLA operations, an algorithm that takes \({\cal U}_{\matA }\) and outputs \({\cal U}_{\matA _{p}}\).

References

• [1]  Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), volume 14, pages 636–647. LIPIcs, 2012.

• [2]  Dong An and Lin Lin. Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm. ACM Transactions on Quantum Computing, 3(2):1–28, 2022.

• [3]  Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195–202, 2017.

• [4]  Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1–33:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

• [5]  Andrew M Childs, Robin Kothari, and Rolando D Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950, 2017.

• [6]  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.

• [7]  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 Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019.

• [8]  Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103(15):150502, 2009.

• [9]  Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 49:1–49:21, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

• [10]  Iordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Physical Review A, 101(2):022316, 2020.

• [11]  Lin Lin and Yu Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020.

• [12]  John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang. Grand unification of quantum algorithms. PRX Quantum, 2(4):040203, 2021.

• [13]  Vivek V Shende, Stephen S Bullock, and Igor L Markov. Synthesis of quantum logic circuits. In Proceedings of the 2005 Asia and South Pacific Design Automation Conference, pages 272–275, 2005.

• [14]  Yigit Subasi, Rolando D Somma, and Davide Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Physical Review Letters, 122(6):060504, 2019.

• [15]  Liron Mor Yosef, Shashanka Ubaru, Lior Horesh, and Haim Avron. Multivariate trace estimation using quantum state space linear algebra. arXiv preprint arXiv:2405.01098, 2024.