Block encoding implementation of matrix product operators*

Qubitization has recently emerged as an innovative and versatile algorithm in the quantum simulation area and beyond. It can be traditionally split into two separate routines: block encoding, which encodes a Hamiltonian in a larger unitary, and signal processing, which applies almost any polynomial transformation to such a Hamiltonian using rotation gates [1]. Block encoding typically constitutes the bottleneck of the entire operation and several problem-specific techniques were introduced to overcome this problem [2, 3].

Our work presents a method to block-encode a Hamiltonian based on its matrix product operator (MPO) representation. Specifically, we encode every MPO tensor in a larger unitary of dimension D + 2, where D is the number of subsequently contracted qubits. Given any system of size L, the total amount of ancillaries for our block encoding scales as O(L + D), while the circuit’s decomposition in one and two-qubit gates requires O(L2^D+2 ) operations.

[1] J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, Grand unification of quantum algorithms, PRX Quantum 2, 040203 (2021).

[2] D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush, Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization, Quantum 3, 208 (2019).

[3] S. Takahira, A. Ohashi, T. Sogabe, and T. S. Usuda, Quantum algorithms based on the block-encoding framework for matrix functions by contour integrals (2021), arXiv:2106.08076 [quant-ph].