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].