Scalable Preparation of Matrix Product States with Sequential and Brick Wall Quantum Circuits

1. Problem Statement

Preparing arbitrary quantum states on near-term quantum devices is a fundamental challenge because it generally requires resources that scale exponentially with the number of qubits ($O(2^N)$). While Matrix Product States (MPS) offer a way to represent physically relevant states (those with limited entanglement) efficiently, preparing them as quantum circuits remains difficult.

Existing approaches suffer from specific trade-offs:

• Heuristic Methods (e.g., SMPD, BMPD): These are deterministic and classically simulable but often suffer from rapid saturation in fidelity as the number of circuit layers increases.
• Variational Optimization (e.g., Evenbly-Vidal, Riemannian): These can achieve high fidelities but scale poorly with system size due to "barren plateaus" (vanishing gradients) and high computational complexity when initialized randomly.

The paper addresses the need for a scalable, end-to-end framework that combines the deterministic efficiency of heuristic methods with the high-fidelity refinement of variational optimization, specifically targeting systems of 19–50 qubits.

2. Methodology: The QSP Pipeline

The authors propose a unified pipeline (illustrated in Fig. 1 of the paper) consisting of four main stages:

Step 1: Compression into MPS

Target states (either physical ground states or classical datasets encoded as probability amplitudes) are converted into an MPS representation.

• Methods: Standard Singular Value Decomposition (SVD) or Tensor Cross Interpolation (TCI).
• Efficiency: TCI allows constructing the MPS using only $O(N\chi^2)$ queries to the probability amplitudes, avoiding the need to load all $2^N$ amplitudes into memory.

Step 2: Qubit Reordering

To minimize circuit depth and bond dimensions, qubits are reordered to place strongly correlated pairs adjacent to each other in the MPS chain.

• Metric: Quantum Mutual Information (QMI) is calculated between all qubit pairs.
• Optimization: The reordering problem is formulated as a Quadratic Assignment Problem (QAP), an NP-hard combinatorial optimization problem. The authors use heuristic solvers (Fast Approximate QAP and 2-opt) to find the optimal permutation.

Step 3: Heuristic Initialization (Warm Start)

The reordered MPS is used to construct an initial quantum circuit using two distinct disentangler architectures:

• Sequential Matrix Product Disentangler (SMPD): A staircase-like architecture. The authors utilize three "enhancements":
  1. Isometry Decomposition: Reducing 2-qubit unitaries to 2 CNOTs (instead of 3) by exploiting the specific structure of the gates.
  2. Gate Pruning: Removing 2-body gates on bonds that have already been disentangled (rank-1).
  3. Mixed Canonical Gauge: Using a mixed gauge to reduce circuit depth by up to 50% compared to left/right canonical forms.
• Brick Wall Matrix Product Disentangler (BMPD): A brick-wall architecture based on the $\Gamma$-$\Lambda$ gauge. It optimizes local unitaries to minimize Rényi entropy layer-by-layer, ensuring the MPS form is preserved during classical simulation.

Step 4: Variational Optimization

The heuristic circuits serve as a "warm start" for variational optimization to refine the state fidelity.

• Algorithms:
  • Evenbly-Vidal (EV): Sweeps through gates, optimizing one at a time using SVD of the environment tensor. It maintains the MPS form, allowing for deep circuits.
  • Riemannian Optimization: Directly optimizes the matrix elements of unitary gates on the unitary manifold using gradient descent (Adam optimizer). This is a global optimizer but computationally expensive for deep circuits due to tensor contraction costs.
• Strategy: The pipeline supports both "one-shot" optimization (optimize the whole pre-built circuit) and "interleaved" optimization (add a layer, optimize, add a layer, etc.).

3. Key Contributions

1. End-to-End Framework: The first comprehensive pipeline combining sequential (SMPD) and brick-wall (BMPD) heuristics with both EV and Riemannian optimizers for MPS preparation.
2. Qubit Reordering via QAP: A rigorous mapping of the qubit reordering problem to the Quadratic Assignment Problem, utilizing QMI to minimize entanglement entropy across bonds.
3. Refutation of Exponential Scaling in SMPD: The authors challenge previous findings (Ref. [29]) suggesting SMPD requires an exponentially large bond dimension ($\tilde{\chi} \sim O(2^L)$) for $L$ layers. They demonstrate that $\tilde{\chi} \sim O(\chi)$ (where $\chi$ is the target bond dimension) is sufficient, making deep SMPD circuits classically simulable.
4. Gate Count and Depth Reduction: Implementation of specific enhancements (isometry decomposition, mixed gauge) that reduce CNOT counts by ~33% and circuit depth by up to 50%.
5. Benchmarking on Real Data: Evaluation on four diverse datasets:
   • Gaussian and Lévy probability distributions (smooth functions).
   • Lorenz attractor (chaotic time-series).
   • S&P 500 stock prices (financial time-series).

4. Results

• Classical Datasets: The pipeline successfully prepared states for systems ranging from 19 to 50 qubits with infidelities ranging from $10^{-7}$ (Gaussian) to $10^{-2}$ (complex datasets like S&P 500).
• SMPD vs. BMPD:
  • SMPD generally achieves lower CNOT gate counts and is superior for simple states (Gaussian, Lévy).
  • BMPD generally achieves lower CNOT circuit depth, making it preferable for deep circuits and complex states (Lorenz, S&P 500).
• Optimization Performance:
  • Evenbly-Vidal (EV) outperformed Riemannian optimization in terms of final fidelity for deep circuits. EV can handle up to $L=200$ layers because it retains the MPS structure, whereas Riemannian optimization is limited to $L \approx 10-15$ layers due to exponential memory growth in tensor contractions.
  • Warm Starts: Initializing variational optimization with heuristic circuits significantly mitigates barren plateaus and accelerates convergence.
• Qubit Reordering:
  • For Gaussian and Lévy distributions, the standard ordering was already optimal.
  • For the S&P 500 dataset, reordering reduced the cost function by ~28% and decreased maximal bond entanglement by up to 20%, though the impact on final state preparation fidelity was minor for this specific dataset.
• Enhancements: The decomposition of isometries into 2 CNOTs (instead of 3) reduced gate counts without sacrificing fidelity, particularly beneficial for shallow circuits.

5. Significance and Conclusion

This work provides a principled and scalable protocol for preparing Matrix Product States on near-term quantum devices (NISQ). By bridging the gap between deterministic heuristic constructions and variational optimization, the authors demonstrate that high-fidelity state preparation is feasible for systems with 50+ qubits, provided the entanglement structure is managed correctly.

The findings suggest that:

1. Hybrid approaches are essential: Heuristics provide a necessary "warm start" to avoid barren plateaus.
2. Architecture choice matters: SMPD is better for gate-count constrained devices, while BMPD is better for depth-constrained devices.
3. Classical simulability: Deep disentangler circuits are more classically simulable than previously thought, allowing for robust verification before deployment on quantum hardware.

This framework supports utility-scale applications in quantum chemistry, optimization, and machine learning where efficient state preparation is a prerequisite for quantum advantage.