Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques

This lecture note series presents tensor network algorithms, specifically Matrix Product States and Operators, as general linear algebra tools for handling exponentially large systems, providing detailed proofs and applications ranging from quantum simulation to solving partial differential equations via the "quantics" representation.

The Gist

The Big Idea: The "Impossible" Library

Imagine you have a library with $2^{50}$ books (that's more than the number of atoms in your body). A quantum computer is a magical machine designed to flip through these books incredibly fast. However, there's a catch: you can't read the whole library at once. You can only peek at one book at a time (a "sample").

The paper asks a provocative question: Can a regular, old-school computer (a classical supercomputer) do the same job as this magical quantum machine?

Usually, the answer is "No," because the library is too big to fit in memory. But the authors argue that many of these "libraries" have a hidden secret: they aren't actually random chaos. They have a simple, repetitive structure, like a fractal or a pattern. If you know the pattern, you don't need to store every single book; you just need to store the instructions on how to build them.

This paper teaches you how to find those patterns using a tool called Tensor Networks.

---

The Main Tool: The "Lego" Approach (Tensor Networks)

The authors introduce a mathematical technique called Tensor Networks. Think of a giant, complex 3D object (like a massive sculpture) that represents a quantum state.

• The Problem: Trying to describe the whole sculpture at once requires a billion numbers.
• The Solution (Tensor Networks): Instead of describing the whole thing, you break it down into small, simple Lego bricks.
  • MPS (Matrix Product States): These are like a long chain of Lego bricks. Each brick connects to the next. If the sculpture isn't too "twisted" (entangled), you can rebuild the whole thing using just a few small bricks.
  • MPO (Matrix Product Operators): These are like Lego instructions or tools that tell you how to change the sculpture (like a gate in a quantum circuit).

The paper shows that for many problems, you don't need the whole billion-number library. You just need the chain of Lego bricks. This allows a regular computer to simulate what a quantum computer does, but much faster and with less memory.

The "Magic" Learning Algorithm (TCI)

One of the coolest parts of the paper is an algorithm called Tensor Cross Interpolation (TCI).

• The Analogy: Imagine you are trying to guess the shape of a hidden mountain range. You can't see the whole thing, but you can ask a guide, "What is the height at this specific spot?"
• How it works: Instead of asking about every single spot (which would take forever), TCI is a smart detective. It asks about a few strategic spots, figures out the pattern, and then fills in the rest of the map.
• The Result: It can learn the shape of a complex function (like a wave or a heat distribution) by only looking at a tiny fraction of the data. It turns a "black box" problem into a set of Lego instructions (an MPS) that a computer can easily handle.

The "Quantics" Trick: Zooming In and Out

The paper introduces a concept called Quantics for solving physics equations (like heat spreading or waves moving).

• The Analogy: Imagine a map of a country. Usually, you look at the whole country at once. But what if you could zoom in on a city, then a street, then a house, all at the same time?
• The Trick: The authors represent numbers in binary (0s and 1s). The first bit tells you if you are on the left or right side of the country (big scale). The next bit tells you if you are in the north or south of that side (medium scale). The last bit tells you if you are on the left or right of your specific house (tiny scale).
• Why it helps: By arranging the data this way, the computer sees that "big scale" changes and "tiny scale" changes are often independent. This makes the "Lego chain" (MPS) very short and easy to compute.
• The Result: They can solve equations on a grid with trillions of points on a regular laptop. A normal computer would crash trying to hold that many points in memory, but the "Quantics" Lego trick compresses it down to something manageable.

The "Quantum Supremacy" Reality Check

The paper discusses the famous "Quantum Supremacy" experiments (where companies claim their quantum computers did something impossible for classical ones).

• The Paper's View: The authors are skeptical of the hype. They argue that those experiments were designed to create "random noise" (a chaotic mess with no pattern). Of course, a classical computer struggles to simulate random noise!
• The Catch: If the quantum computer is doing something useful (like simulating a chemical reaction or a specific material), the state usually has a lot of structure. The paper shows that classical computers, using these Lego techniques, can actually simulate those useful quantum states very well.
• The Verdict: A quantum computer isn't a magic wand that solves everything. It's a specific tool. If the problem has a "low-rank" structure (simple Lego patterns), a classical computer can often beat the quantum one.

Summary of What They Did

1. Taught the basics: How to break down huge math problems into small, connected pieces (Tensor Networks).
2. Showed how to simulate quantum computers: They built a "virtual" quantum computer on a regular laptop that can handle hundreds of qubits, provided the circuit isn't too chaotic.
3. Introduced a learning tool (TCI): A way to teach a computer the shape of a problem just by peeking at a few data points.
4. Solved real-world physics: They used these tools to solve complex equations (like heat flow and wave equations) on grids so huge they would normally be impossible, all on a standard workstation.

The Bottom Line

The paper claims that classical computers are not doomed. As long as the problem has some underlying structure (which most useful scientific problems do), we can use "Tensor Networks" to compress the data and solve it. We don't always need a quantum computer to do the heavy lifting; sometimes, a clever classical algorithm can compete, and even win.

Technical Summary

Technical Summary: "Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques"

Problem Statement
The paper addresses the fundamental challenge of simulating quantum systems and solving high-dimensional linear algebra problems that scale exponentially with system size ($2^N$ for $N$ qubits). While quantum computers are theoretically capable of manipulating these exponentially large state spaces, classical supercomputers cannot store the full wavefunction for $N \gtrsim 50$. However, the authors note that many physically relevant states possess internal mathematical structures that allow for efficient classical representation. The core problem is to identify and exploit these structures—specifically low-rank properties—to perform matrix-vector multiplications, solve eigenvalue problems, and simulate dynamics without explicitly storing the full exponential object. The lectures aim to disentangle tensor network algorithms from their traditional many-body physics context to present them as general tools for linear algebra on large matrices and vectors.

Methodology
The paper presents a comprehensive suite of algorithms based on Matrix Product States (MPS) and Matrix Product Operators (MPO). These are tensor network representations that factorize exponentially large vectors and matrices into a chain of small, local tensors connected by virtual indices (bond dimensions).

1. Exact Emulation: The authors first establish that quantum circuits are tensor networks. They describe exact emulation strategies:

   • Full State Simulator: Allocates a vector of size $2^N$ and applies gates sequentially. This scales exponentially in memory ($O(2^N)$) but linearly in the number of gates.
   • Exact MPS Emulator: Represents the state as an MPS. For circuits with limited entanglement (e.g., nearest-neighbor gates on product states), this scales linearly in $N$ and polynomially in circuit depth, provided the bond dimension $\chi$ remains small.

2. Compression and Approximation: To handle larger systems, the lectures introduce low-rank compression via Singular Value Decomposition (SVD).

   • Canonical Form: A gauge choice where tensors are isometries, allowing the entanglement entropy to be read directly from the singular values of a central tensor.
   • TEBD (Time-Evolving Block Decimation): An algorithm for quantum circuits where gates are applied, and the resulting state is truncated via SVD to maintain a fixed bond dimension $\chi$. This introduces a controlled error bounded by the discarded singular values.
   • DMRG (Density Matrix Renormalization Group): Adapted here for quantum circuits and Hamiltonian diagonalization. It optimizes one or two tensors at a time to minimize the energy (for Hamiltonians) or maximize fidelity (for circuits), sweeping through the system until convergence.

3. Learning and Construction (TCI): A significant portion of the methodology is dedicated to Tensor Cross Interpolation (TCI). Unlike traditional methods that require access to the full tensor, TCI is an active learning algorithm that constructs an MPS/MPO representation by querying a function $F(\sigma)$ at specific indices.

   • It utilizes Cross Interpolation (CI) and Partial Rank-Revealing LU (prrLU) decomposition to select "pivots" (rows and columns) that maximize the determinant (maxvol principle), ensuring the selected slices capture the essential information of the matrix.
   • This allows the conversion of arbitrary functions (e.g., integrands, potentials) into MPS/MPO formats without prior knowledge of their tensor structure.

4. The "Quantics" Representation: The authors introduce a specific discretization scheme where a continuous variable $x$ is mapped to a binary string of bits. This "quantics" representation allows functions of continuous variables to be treated as MPS.

   • They provide analytical constructions of MPOs for differential operators (differentiation, integration, Laplacian), convolution, and the Quantum Fourier Transform (QFT).
   • Crucially, the QFT is shown to be a low-rank MPO (rank $\chi \approx 15$ for machine precision), enabling "superfast" Fourier transforms on grids with $2^N$ points.

Key Contributions

• Generalization of Tensor Networks: The lectures reframe MPS and MPO not merely as tools for condensed matter physics but as general linear algebra solvers for exponentially large vectors and matrices.
• Algorithmic Toolbox: The text provides detailed, step-by-step derivations for:
  • Sampling from MPS (exact sampling via Bayesian chain rule).
  • Adding and multiplying MPS/MPOs.
  • Solving linear systems ($Ax=b$) using MPS.
  • Constructing MPOs for differential operators and the QFT analytically.
• TCI as a Gateway: The paper positions TCI as the critical bridge allowing non-tensor-network problems (like Partial Differential Equations) to be mapped into the tensor network framework.
• Quantics for PDEs: The authors demonstrate how the quantics representation, combined with TCI and low-rank MPOs, allows for the solution of PDEs (Poisson, Schrödinger, Heat equation) on grids with $2^{30}$ to $2^{40}$ points using standard workstations, a scale unreachable by brute-force methods.

Results
The paper illustrates these methods through several concrete applications:

• Quantum Circuit Simulation: Comparisons show that for circuits with low entanglement (e.g., GHZ state generation), the exact MPS emulator scales as $\sim N^2$, whereas the full state simulator scales as $\sim N 2^N$.
• Random Circuits and Fidelity: Simulations of random quantum circuits (similar to "quantum supremacy" experiments) show that fidelity decays exponentially with circuit depth, controlled by the bond dimension. This suggests that even for large $N$, if the error rate (or effective bond dimension) is low enough, tensor networks can simulate the system.
• PDE Solutions:
  • Integration: TCI is used to compute a 10-dimensional oscillatory integral, converging as $\sim 1/N_{eval}^4$, significantly outperforming Monte Carlo methods which suffer from the sign problem and scale as $1/\sqrt{N_{eval}}$.
  • Heat Equation: Using the low-rank QFT MPO, the heat equation is solved on a grid of $2^{30}$ points (one trillion points) in seconds on a laptop.
  • Gross-Pitaevskii Equation: Simulations of this nonlinear equation on a quasiperiodic potential are performed with $2^{20}$ grid points per dimension, demonstrating the ability to handle vastly different length scales.

Significance and Claims
The authors claim that these "quantum-inspired" techniques compete directly with the capabilities of quantum computers by exploiting the same underlying mathematical structures (low entanglement/low rank) that make quantum states tractable.

• Reframing Quantum Supremacy: The paper argues that "quantum supremacy" experiments often target random, chaotic states that are difficult to simulate but may lack physical relevance. Conversely, many useful quantum algorithms and physical systems possess structure that allows classical tensor networks to simulate them efficiently.
• I/O Bottleneck: The authors highlight that quantum computers face an "I/O bottleneck" (outputting only $N$ bits of probabilistic information), whereas tensor networks can provide the full wavefunction or high-precision integrals.
• Future Outlook: The paper posits that tensor networks and TCI will play a pivotal role in the future of quantum computing, potentially serving as the interface to map problem inputs into tensor network formats that can then be compiled into quantum circuits. The authors emphasize that while tensor networks are powerful, they are not a panacea; they rely on the existence of low-rank structure, which is not guaranteed for all problems.

In summary, the paper serves as a pedagogical and technical guide demonstrating that classical tensor network algorithms, particularly when augmented by TCI and the quantics representation, offer a robust, scalable, and often superior alternative to brute-force simulation for a wide class of high-dimensional problems, effectively challenging the necessity of quantum hardware for specific tasks.