Faster matrix product state preparation by exploiting symmetry-induced block-sparsity

summary

The gist

The gist: The work develops improved methods for preparing matrix product states by exploiting symmetry-induced block-sparsity to reduce Toffoli cost and achieve significant improvements in resource

In short

The work improves matrix product state (MPS) preparation by using symmetry-induced block-sparsity from global U(1) symmetries. This allows transforming tensors into block-diagonal forms, enabling efficient unitary synthesis. By modifying unitary synthesis with Givens rotations for real unitaries, the Toffoli cost for preparing these states is reduced by a factor of $\sqrt{2}$, leading to significant resource savings.

Key concepts

Matrix Product States (MPS): MPS are a mathematical structure used to represent quantum states efficiently, especially in condensed matter physics and quantum chemistry. They are composed of tensors that describe how local quantum systems interact, and preparing them on a quantum computer is computationally expensive.
Symmetry-Induced Block-Sparsity: Global symmetries like particle number conservation restrict the structure of MPS tensors, forcing them into a block-sparse format. This means most entries in the tensor are zero, which dramatically reduces the computational resources needed for preparation compared to dense matrices.
Unitary Synthesis via Givens Rotations: This is a method used to construct complex quantum gates (unitaries) by breaking them down into simpler building blocks, specifically Givens rotation matrices. For real-valued unitaries, choosing specific rotation angles simplifies the decomposition, removing costly Rz gates and reducing the required Toffoli cost by about $\sqrt{2}$.
Toffoli Cost: The Toffoli cost measures the number of elementary quantum gates (like CNOTs) required to implement a specific unitary operation. Lowering this cost is crucial for making quantum state preparation feasible on current or near-future quantum hardware.

Terminology used across episodes

Reinforcement Learning (RL) — explained in 26 episodes
Flow Matching — explained in 22 episodes
Quantum Fisher Information (QFI) — explained in 21 episodes
Retrieval-Augmented Generation (RAG) — explained in 21 episodes
Sample Complexity — explained in 20 episodes
Federated Learning — explained in 18 episodes

This episode discusses

The paper

Faster matrix product state preparation by exploiting symmetry-induced block-sparsity · Read on arXiv

Institute of Quantum Technologies, German Aerospace Center · Center for Integrated Quantum Science and Technology (IQST), Ulm University

Matrix product states (MPS) serve as a key tool for studying quantum systems from chemistry and condensed-matter physics, making their preparation on quantum computers an important task in interfacing classical and quantum simulation. Many systems of interest have U(1) -symmetries induced by particle number and spin projection conservation, allowing to restrict the MPS tensors to be of block-sparse form, a property widely used in the implementation of classical algorithms such as the density matrix renormalization group. We reduce the cost of fault-tolerantly preparing block-sparse MPS within the standard ancilla-assisted linear-depth approach by implementing row and column permutations that transform the block-sparse matrices into block-diagonal form. These block-diagonal unitaries are then implemented via unitary synthesis, with the cost being determined by the size of the largest block. In this context, we modify the unitary synthesis approach of Berry et al. in order to reduce the Toffoli cost for real-valued unitaries by a factor of sqrt 2. In numerical benchmarks, we achieve Toffoli cost improvement factors of 10 - 30 compared to the state-of-the-art for MPS of various molecular systems.

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Faster matrix product state preparation by exploiting symmetry-induced block-sparsity".

Mira: Here's the gist of the paper. The gist: The work develops improved methods for preparing matrix product states by exploiting symmetry-induced block-sparsity to reduce Toffoli cost and achieve significant improvements in resource requirements for quantum state preparation.

Kai: Exploiting Symmetry-Induced Block-Sparsity The paper addresses the difficulty in preparing matrix product states (MPS) on quantum computers by leveraging U(1)-symmetries induced by particle number and spin projection conservation, which restrict MPS tensors to be of block-sparse form The main idea is to exploit this block-sparsity by implementing row and column permutations that transform the block-sparse matrices into a block-diagonal form These resulting block-diagonal unitaries are then implemented via unitary synthesis, with the cost being determined by the size of the largest block The authors modify the unitary synthesis approach of Berry et al.

Mira: in order to reduce the Toffoli cost for real-valued unitaries by a factor of √2.

Kai: Unitary Synthesis via Givens Rotations The paper develops a variation of the unitary synthesis approach of Berry et al.

Title and authors: Kai: Now, let's look at what this paper actually suggests about how we get these states ready. They call it "Faster matrix product state preparation by exploiting symmetry-induced block-sparsity."

Mira: It’s essentially saying that because of those symmetries, the matrices we are working with aren't as big and messy as they seem, which lets us use clever tricks to make the preparation faster.

Lev: The paper mentions reducing the cost by transforming those block-sparse matrices into a block-diagonal form using row and column permutations.

Kai: And once you have that block-diagonal form, instead of doing one big unitary synthesis, you only need to worry about the size of the largest block, which is much smaller.

The paper's summary: Mira: So the summary is that they take a standard method for preparing MPS and modify it by using row and column permutations to get that block-diagonal form we just talked about.

Kai: Then they use unitary synthesis on those blocks, which means the cost depends only on the size of the largest block, not the full matrix dimension.

Lev: For a fermionic system, they show how local Hilbert spaces are spanned by a joint eigenbasis of size D, and because of those symmetries, this leads to tensors M i and U'i having that block-sparse structure.

Mira: The main goal here is implementing the unitaries U i equals U'i star, where that new matrix U' i is a (four times chi) by chi matrix.

The paper's improvements: Kai: The paper introduces a specific improvement in the unitary synthesis approach, which they call "Unitary Synthesis via Givens Rotations." This modification is for real-valued unitaries.

Lev: They use Givens rotation matrices G(theta, phi) as building blocks for this decomposition of U = Ck · · · C1.

Mira: And here's the key part: for real unitaries, they can choose the angle phi to be zero in some layers, which removes those Rz gates from the decomposition entirely.

Kai: This leads to a decomposition like U = DLl · · ·L1 where each block is given by Ry(theta)Rz(phi prime), which effectively reduces the Toffoli cost for real unitaries by a factor of the square root of two.

Conclusion: Mira: So to wrap up, they show that this approach, using symmetry-induced block-sparsity and Givens rotations for real unitaries, gives us a way to prepare higher-quality initial states.

Kai: The benchmark results on various molecular systems show Toffoli cost improvement factors of around ten to thirty compared to the state of the art.

Lev: For real MPS, they calculate the Toffoli cost by replacing all occurrences of two b by b and all chi plus one by chi, showing a reduction in complexity.

Kai: This work is important because it means we can get better starting points for quantum phase estimation, which could help us bring down the end-to-end cost for ground-state energy estimation later on.

Mira: The paper "Faster matrix product state preparation by exploiting symmetry-induced block-sparsity" sets a new path for preparing MPS in real applications.

Lev: For me, it's interesting because implementing this relies on outsourcing the Givens decompositions to Rust code, which is pretty practical for real hardware deployment.

Kai: So it looks like this approach could become a key part of connecting classical and quantum simulation in chemistry and condensed matter physics.

More episodes

← Home