⚛️ quantum physics

High performance Boson Sampling simulation via data-flow engines

This paper presents a high-performance Boson Sampling simulator that generalizes the BB/FG permanent formula using n-ary Gray code ordering and implements it on FPGA-based data-flow engines to achieve efficient sampling from a 60-mode interferometer with up to 40 photons.

Original authors: Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi, Zoltán Kolarovszki, Uroš Stojčić, Tamás Kozsik, Oskar Mencer, Michał Oszmaniec, Zoltán Zimborás, Péter Rakyta

Published 2026-04-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gregory Morse, Tomasz Rybotycki, Ágoston Kaposi, Zoltán Kolarovszki, Uroš Stojčić, Tamás Kozsik, Oskar Mencer, Michał Oszmaniec, Zoltán Zimborás, Péter Rakyta

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Impossible" Puzzle

Imagine you are trying to predict the outcome of a very complex game of billiards, but instead of 15 balls, you have 40 invisible, magical balls bouncing around inside a maze of mirrors (an optical interferometer).

In the quantum world, these balls (photons) don't just bounce; they exist in many places at once and interfere with each other like waves. To predict where they will end up, you have to solve a massive mathematical puzzle called calculating the "Permanent" of a matrix.

The Problem:
For a normal computer (like your laptop or a supercomputer), solving this puzzle for 40 balls is like trying to count every grain of sand on Earth, one by one, while the sand keeps multiplying. It takes so long that by the time you finish, the universe might have ended. This is why "Quantum Supremacy" is a big deal: quantum computers can do this instantly, but we need to prove they are actually doing it right. To do that, we need a classical computer to act as a referee and check the quantum computer's work. But our referees are too slow!

The Solution: A Specialized Factory (The FPGA)

The authors of this paper built a super-fast "referee" using a special type of computer chip called an FPGA (Field Programmable Gate Array).

Think of a normal CPU (your computer's brain) as a generalist chef. It can cook anything, but it does it one dish at a time, chopping, frying, and plating sequentially. Even if you give it a recipe for 1,000 dishes, it still has to do them one after another.

The FPGA, however, is like a massive, custom-built factory assembly line.

Instead of one chef, you build a specific machine where every single worker (transistor) has one job: "Add these two numbers," or "Multiply these two numbers."
Once the assembly line is built, data flows through it like water in a river. While the first worker is processing the first number, the second worker is already processing the second number, and the third is on the third.
The paper describes building this factory specifically to solve the "Permanent" puzzle. They didn't just make it faster; they made it a dedicated machine that never stops moving.

The Secret Sauce: The "Gray Code" Shortcut

Even with a super-fast factory, the math is still too hard. The formula to solve the puzzle involves adding up billions of different combinations.

The authors used a clever trick called Gray Code ordering.

The Analogy: Imagine you are trying to taste every possible combination of toppings on a pizza.
- The Slow Way: You make a pizza with pepperoni, taste it. Then you make a new one with pepperoni and mushrooms, taste it. Then you make a new one with pepperoni, mushrooms, and olives. You have to rebuild the whole pizza every time.
- The Gray Code Way: You start with pepperoni. To get the next pizza, you only change one thing (add mushrooms). To get the next, you only change one thing (remove pepperoni). You never rebuild the whole pizza; you just tweak the previous one.
Why it matters: This saves a massive amount of time because the factory doesn't have to recalculate everything from scratch. It just updates the previous result.

Handling the "Crowded" Modes (Row Multiplicities)

In these quantum experiments, sometimes multiple photons land in the exact same exit slot (mode).

The Old Way: If 5 photons land in the same slot, the computer treats them as 5 separate, distinct events and does the math 5 times.
The New Way: The authors realized that if 5 photons land in the same spot, the math is repetitive. They created a "Group Discount" system. Instead of calculating 5 separate things, they calculate the group effect once and multiply the result. This is like realizing you don't need to count 5 apples individually if you know you have a bag of 5; you just count the bag.

The Results: How Fast is Fast?

The team put this factory on 4 FPGA chips working together.

The Achievement: They managed to simulate a quantum experiment with 40 photons and 60 exit slots.
The Speed: It took them about 80 seconds to generate one single sample (one possible outcome).
The Comparison:
- A standard supercomputer would take years to do this.
- A real quantum experiment (the one they are trying to verify) took 26 hours to get just 150 samples.
- Their simulator can do the math for a similar setup in less than a second (if the photons are lost/missing, which happens in real life, it takes about 6 minutes).

Why This Matters

This isn't just about being fast; it's about trust.
If a quantum computer claims it solved a problem, how do we know it's not cheating? We need a classical computer to say, "Yes, that result is statistically correct."

Before this paper, classical computers were too slow to act as referees for large quantum experiments.
Now, with this "Factory on a Chip," we can verify quantum computers with 40+ photons. This bridges the gap between the theoretical promise of quantum computing and the reality of proving it works.

Summary in One Sentence

The authors built a specialized, assembly-line computer chip that uses a clever "one-change-at-a-time" math trick to solve a nearly impossible quantum puzzle in minutes, allowing us to finally verify that quantum computers are actually doing what they claim to do.

1. Problem Statement

Boson Sampling (BS) is a leading candidate for demonstrating quantum computational advantage. It involves sampling from the probability distribution of indistinguishable photons passing through a linear optical interferometer.

Computational Bottleneck: The probability of a specific output configuration is proportional to the permanent of a sub-matrix of the interferometer's unitary matrix. Calculating the permanent of an $n \times n$ matrix is a #P-complete problem with no known polynomial-time classical algorithm.
Scalability Issues: Standard classical simulations scale exponentially ( $O(n \cdot 2^n)$ or $O(n^2 \cdot 2^n)$ ). As photon numbers ( $n$ ) and mode counts ( $m$ ) increase, classical simulation becomes intractable, hindering the validation of quantum supremacy experiments.
Specific Challenges:
- Photon Collisions: In realistic experiments, multiple photons may occupy the same output mode, leading to repeated rows in the unitary matrix. Standard algorithms do not efficiently exploit this redundancy.
- Numerical Accuracy: High-precision floating-point arithmetic is required to avoid errors, but this is computationally expensive on standard CPUs.
- Hardware Limitations: Traditional CPU/GPU parallelism struggles with the high data dependency and memory bandwidth requirements of permanent calculations.

2. Methodology

The authors propose a novel approach combining a mathematical generalization of the permanent formula with a specialized hardware architecture.

A. Algorithmic Innovation: Generalized BB/FG Formula

The authors generalize the Balasubramanian-Bax-Franklin-Glynn (BB/FG) formula to handle row and column multiplicities (photon collisions).

Standard BB/FG: Uses binary Gray code ordering to reduce complexity from $O(n^2 \cdot 2^n)$ to $O(n \cdot 2^n)$ by reusing partial sums.
n-ary Gray Code Extension: To account for $M_k$ $M_{k}$ photons in the $k$ $k$ -th output mode (resulting in $M_k$ $M_{k}$ identical rows), the authors replace the binary Gray code with an n-ary (non-Boolean) Gray code.
- The digits of the counter range from $0$ to $M_k$ instead of $0$ to $1$.
- This allows the algorithm to skip redundant calculations, reducing the effective complexity to $O(n \cdot 2^{M^*})$ , where $M^* = \sum \log_2(M_k + 1)$ .
Numerical Stability: The BB/FG formula is chosen over Ryser's formula because it offers superior numerical accuracy in fixed-point arithmetic, a critical factor for FPGA implementation.

B. Hardware Implementation: Data-Flow Engines (DFEs)

The algorithm is implemented on FPGA-based Data-Flow Engines (specifically Xilinx Alveo U250 cards) using the Maxeler Technologies framework.

Data-Flow Model: Unlike traditional von Neumann architectures, DFEs stream data through a static pipeline of hardware resources. Each clock cycle, a new data element is processed, allowing for massive concurrency even with high data dependencies.
Fixed-Point Arithmetic: To maximize FPGA resource efficiency and speed, the authors use fixed-point arithmetic rather than floating-point.
- Input unitaries (64-bit double precision) are converted to fixed-point.
- Bit-width is dynamically increased from 64 bits up to 192/256 bits during the calculation tree to maintain precision comparable to extended-precision CPU implementations.
Architecture Design:
- Matrix Partitioning: The input matrix is split into four blocks to utilize the four Super Logic Regions (SLRs) of the FPGA chip.
- Pipeline Stages:
  1. Column Sum Kernels: Calculate initial column sums and stream $\delta$ vectors using the n-ary Gray code logic.
  2. Product Kernels: Perform complex number multiplications (using optimized Karatsuba-style formulas) in a binary tree reduction.
  3. Summation Kernel: Accumulates the final results.
Batch Processing: To amortize the PCIe communication and initialization overhead, the system processes batches of multiple matrices in a single FPGA execution.

3. Key Contributions

Generalized BB/FG Algorithm: First application of n-ary Gray code ordering to the BB/FG formula to explicitly handle photon multiplicities, significantly reducing computational complexity for collision-heavy scenarios.
FPGA Acceleration: Development of a scalable, high-performance permanent calculator on FPGAs that supports arbitrary matrix sizes (up to $40 \times 40$ ) without reprogramming the chip.
Fixed-Point Precision Strategy: A novel method to achieve extended-precision accuracy (comparable to 128-bit floats) using fixed-point arithmetic on FPGAs, balancing speed and numerical fidelity.
Unified Simulation Framework: Integration of the DFE accelerator into the Piquasso Python framework, enabling simulation of both ideal and lossy Boson Sampling experiments.

4. Results

The authors benchmarked their system against state-of-the-art CPU implementations (Piquasso Boost and TheWalrus) and theoretical estimates.

Performance Speedup:
- For matrices larger than $n \approx 13$ , the DFE implementation outperforms CPU implementations.
- At 40 photons, the DFE is approximately 7.4 times faster than the double-precision CPU BB/FG implementation and 27.9 times faster than the long-double precision CPU implementation.
- Using 4 concurrent FPGA chips, the system draws a single sample from a 60-mode interferometer with 40 input photons in approximately 80 seconds (ideal case).
Lossy Simulation:
- For a 60-mode interferometer with 30% photon loss (simulating a 40-photon input reduced to fewer detected photons), the sampling time increases to ~360 seconds due to the doubling of effective modes required by the Clifford & Clifford algorithm for lossy BS.
Numerical Accuracy:
- The fixed-point DFE implementation achieves relative errors ( $\epsilon$ ) smaller than $10^{-8}$ for matrix sizes up to $n=40$ , matching the accuracy of extended-precision CPU implementations.
- The BB/FG formula on DFEs proved significantly more accurate than Ryser's formula under the same conditions.
Theoretical Validation:
- The experimental sampling times fit the theoretical complexity model proposed by Clifford & Clifford [1] with a single portable parameter $T_0 = 7.5 \times 10^{-11}$ sec.
- The system is roughly 8.6 times slower than a massive supercomputer (Tianhe-2 with 4096 nodes) for a single $40 \times 40$ permanent, but achieved on a single server with 4 FPGAs.

5. Significance

Validation of Quantum Advantage: This work provides a powerful tool for validating quantum supremacy claims. By simulating Boson Sampling experiments with high fidelity and speed, researchers can verify that quantum devices are performing their intended tasks and not being "spoofed" by classical heuristics.
Scalability: The ability to simulate up to 40 photons on a single server cluster (4 FPGAs) pushes the boundary of classical simulation, allowing for the testing of larger quantum photonic experiments before they are built.
Hardware Efficiency: The study demonstrates that Data-Flow Engines are a superior alternative to GPUs/CPU clusters for specific, highly parallelizable, and data-dependent mathematical problems like permanent evaluation, offering a path toward more efficient quantum simulation hardware.
Portability: The introduction of the $T_0$ parameter allows for a standardized, hardware-agnostic comparison of Boson Sampling simulator performance across different architectures.

In conclusion, the paper presents a breakthrough in classical Boson Sampling simulation by marrying a mathematically optimized algorithm (n-ary Gray code BB/FG) with specialized FPGA hardware, achieving unprecedented speed and accuracy for simulating high-photon-number quantum optical systems.