OnePerc: A Randomness-aware Compiler for Photonic Quantum Computing

Photonic quantum computers are built by merging small entangled states with an operation that succeeds about three quarters of the time and destroys the photons when it fails, so the machine you end up with is never the one you asked for; OnePerc (UC San Diego and Cisco) stops asking — it fires all the merges at once, accepts whatever random structure results, and relies on a phase transition guaranteeing that above a certain success rate a large connected piece almost always exists, then carves a regular lattice out of that piece in real time.

The argument in one glance

Problem

The operation that builds the machine fails a quarter of the time

Photonic hardware scales by generating small entangled states and merging them into larger ones. The merge is probabilistic — about 75 percent in practice — and a failure destroys both photons involved, so the connection cannot be repaired.
What people did

Plan the structure you need, then retry whatever fails

The existing compiler works out exactly which merges produce the entangled structure a program requires. Adding a retry loop on top is the obvious way to cope with failures, and for small programs at optimistic success rates it works.
Why it fell short

Retrying is serial, and photons do not wait

Deciding what to retry depends on what just failed, so merges must run one after another, which stretches each cycle. Some failures are unrecoverable and force the whole compilation to restart. At a realistic 75 percent, a four-qubit program needs more than a million cycles.
This paper's idea

Stop specifying the structure and start harvesting it

Fire every merge at once in a fixed pattern and accept the random result. Above a threshold, a random graph almost certainly contains one enormous connected piece — so search that piece for a regular grid, and hand the program a grid rather than trying to build its exact shape.

Why this problem is worth solving

This machine does not run gates, so the usual compiler stack does not apply.

Photons interact with each other very weakly, which is excellent for keeping qubits from disturbing one another and terrible for building two-qubit gates. The alternative model prepares a large entangled state in advance — a graph state, where every vertex is a qubit and every edge an entanglement between two of them — and then drives the entire computation by measuring qubits one at a time, choosing each measurement angle according to the program and adjusting it based on earlier outcomes. A circuit translates into this form mechanically: single-qubit rotations become measurement angles, and two-qubit gates become edges of the graph. The consequence is that compiling for this platform means building a specific graph, not scheduling a sequence of operations, which is why frameworks designed around circuits do not transfer.

The way that graph gets built is where all the difficulty lives.

Hardware produces small identical entangled states on a periodic clock, arranged as a two-dimensional layer each cycle. Merging two of them is called a fusion: a joint measurement that, on success, joins the two states into one larger one, and on failure destroys both photons involved. Practical success is around 75 percent; raising it is brutally expensive, with 78 percent the best known using eight auxiliary photons and something above 95 percent requiring roughly thirty entangled ones. Percolation is the phenomenon that rescues this. If you connect the points of a grid at random and the connection probability exceeds a threshold — one half for a square lattice — the resulting graph almost certainly contains one giant component spanning the whole thing. Since 75 percent comfortably exceeds one half, a random merge pattern reliably produces something large and connected, even though nobody can say in advance what shape it will be.

What people did before, and where it broke

Assume the merges succeed and plan the exact structure. The prior compiler for this platform does this well, working out a merge pattern that produces precisely the graph a program needs and minimising both depth and merge count. Where it broke. It contains no notion of failure at all, so the state it actually produces is a random subgraph of the intended one and the program simply cannot run on it.
Wrap that plan in a retry loop. The natural repair: when a merge fails, try again using different photons. Where it broke. Each retry depends on the previous outcome, so merges have to run one after another instead of together, which stretches the time spent on each layer of hardware.
Restart the whole compilation on unrecoverable failures. Sometimes retrying is not possible — a run of failures can consume every neighbour a qubit had, leaving it with nothing left to connect to. Where it broke. At 75 percent success this happens often enough that a four-qubit program needs more than a million hardware cycles, and the frequency grows with program size.
Improve the hardware success rate instead. Adding auxiliary photons raises the merge probability, which would make everything easier. Where it broke. The best known result with linear optics is 78 percent using eight auxiliary photons, and passing 95 percent would need around thirty of them, entangled with each other — which is itself the problem being solved.
Just take longer over the real-time decisions. More time means better choices about what to retry and where to route. Where it broke. Photons are stored in optical fibre and leak, giving them a lifetime of roughly five thousand hardware cycles. Time spent thinking is time the quantum state is decaying, so the real-time budget is a physical wall rather than a preference.
The gap. Every approach treats the random structure as damage to be repaired. But repair is serial, sometimes impossible, and always racing a clock set by physics — while the randomness itself has a statistical property nobody was using.

How you compute on a structure you did not choose

From building the graph you want to harvesting the graph you get

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

The randomness stops being an obstacle the moment you stop asking for a particular outcome. The whole difficulty of the prior approach comes from wanting a specific graph: every merge has a job, so every failure is a hole, and the holes have to be patched serially by a process that sometimes runs out of material. The move here is to give up on specifying the shape and specify only a statistical property. Fire all the merges concurrently in a fixed pattern, get back the intended lattice minus a random quarter of its edges, and lean on percolation — the fact that a randomly connected grid undergoes a sharp transition, and above a threshold almost certainly contains one component spanning the whole thing. The threshold for a square lattice is one half and the achievable success rate is three quarters, so the giant component is essentially guaranteed. What is not guaranteed is its shape, and that turns out not to matter, because a graph state can be reduced to any of its subgraphs by measuring the unwanted qubits away. Replacing deterministic control with a guarantee that holds with overwhelming probability, and getting a system that works because of the statistics rather than in spite of them, is the same reframing the row-hammer defence work covered elsewhere on this site performs when it stops trying to protect specific victims and instead makes the attack a lottery nobody wins.

The deadline is physical, so the expensive thinking has to happen before the photons exist. Photons stored in optical fibre leak, giving them about five thousand hardware cycles of life, and every microsecond of classical decision-making is a microsecond of decay. That rules out any clever real-time optimisation, and it is precisely why retrying was fatal — not only because retries are serial but because the deciding is on the critical path. What survives the budget is a mechanical search: check connectivity with a disjoint-set structure, find shortest paths with breadth-first search, and do it in parallel modules across the layer. Everything requiring judgement moves offline, where there is no clock at all. This division is what the paper’s structure is really about, and it is the same division the quantum error-correction decoder work covered elsewhere on this site arrives at from an identical pressure — corrections must land within a microsecond, so the gold-standard matching algorithm is run in advance over every error pattern that can occur and the runtime does nothing but look up the answer.

An intermediate representation is what makes the two halves able to talk. The offline pass needs a target and the online pass produces something random, so something has to stand between them and make a promise both can rely on. That something is described as a virtual machine: a stack of fixed-size two-dimensional grids, one per layer, where any edge within a layer or between layers can be individually switched on or off, and where a node can be parked in memory to connect to a distant future layer. None of that is what the hardware does — the hardware produces a random mess — but all of it is what the reshaping pass can guarantee to deliver, which is the only property that matters. The offline mapper then works against this clean abstraction with ordinary techniques: schedule nodes dynamically from a dependency graph, cap how many partially-connected nodes may occupy a layer at 25 percent so routing space remains, and periodically flush the memory to bound how much classical state the runtime must hold. Supplying the missing layer that lets general programs meet irregular hardware, instead of matching each program to each machine by hand, is the same contribution the sparse tensor abstraction work covered elsewhere on this site makes for accelerators that had each been built around a single expression.

Following one program onto a lattice that does not exist yet

What happens between a quantum circuit and a measurement

The first two steps run before anything is switched on. The rest happen while photons are alive, on a clock of roughly a nanosecond per layer.

Step 1 of 5

Translate the circuit into a graph, then map it onto the virtual machine

The circuit becomes a graph state: rotations become measurement angles on vertices, two-qubit gates become edges. That graph is then embedded into the stack of fixed-size grids, with extra vertices used as wires where two program vertices need to reach each other.

Nodes are scheduled from a dependency graph as they become ready rather than partitioned in advance, and no layer may be more than a quarter occupied by nodes whose edges are still incomplete, so routing space survives.

Why it works

A sharp threshold turns a probabilistic operation into a near-certain guarantee. A quarter of the merges fail and cannot be repaired, so no specific structure can be promised → but connecting the points of a grid at random above a threshold of one half almost certainly yields a single component spanning it, and the achievable rate is three quarters → so a giant connected piece is essentially guaranteed even though its shape is unknown.
Unwanted parts of a graph state can be deleted for free. The giant component is the wrong shape for any particular program → but measuring a qubit in the right basis removes it and its edges cleanly, leaving any chosen subgraph → so the shape problem becomes a search problem inside something you already have.
Concurrency is only possible if nothing depends on what just happened. Retrying failures individually forces merges to run one after another, stretching every layer → so all merges fire together in a pattern fixed before the program is even known → and the time per layer stops depending on how the failures fell.
Making the reshaping target program-agnostic is what keeps it inside the deadline. A structure tailored to the program would require program-specific search under a hard photon-lifetime budget → but aiming at nothing more specific than a regular grid of some size reduces the real-time work to connectivity checks and shortest paths → which can be split into modules and searched in parallel.
An abstraction lets the offline pass be as clever as it likes. The offline mapper has unlimited time and the online pass has almost none, and they must agree on something → so the online pass exposes a virtual machine of fixed grids with individually switchable edges, which is far more regular than the hardware and strictly within what reshaping can deliver → letting ordinary mapping algorithms run against a deterministic target.

What it costs (trade-offs and scope)

None of this ran on hardware, because the hardware does not exist. The evaluation is a simulation against an architectural model taken from prior work, with parameters drawn from a vendor roadmap. The million-qubit photonic machine this targets is a projection.
On small programs it uses far more merges than the baseline, not fewer. At four qubits the merge count is between roughly 1.5 and 20 times worse than the retry-based approach, because a fixed pattern fires everything whether or not it is needed. The advantage appears only beyond four qubits, and the paper reports the losing numbers.
The classical memory demand during execution is enormous. Sixty-four-qubit benchmarks require 192 gigabytes of RAM in the real-time stage. A periodic flush brings 100-qubit programs within 32 gigabytes, at a cost of roughly 13 to 19 percent more hardware cycles.
Whether the real-time work actually fits inside the photon lifetime is not established. The entire design is motivated by a budget of about five thousand nanosecond cycles, and the reported online times are relative — this modular scheme against that non-modular one, in a Python implementation. No absolute claim is made that the connectivity checks and path searches complete in time on a real machine, which is the assumption everything rests on.
Modularity sacrifices a large fraction of the resource. Splitting the layer into parallel modules yields a grid about 60 percent the size of what an unrestricted search would find, because the seams between modules waste space and sometimes fail to join. The defence is that an unrestricted search restricted to the same time does two to six times worse, which is the comparison that matters and is also an argument about relative rather than absolute feasibility.
The clean percolation argument applies to the idealised case. The threshold of one half is for a plain square lattice. The actual construction merges layers to raise connectivity, and those merges fail into tangled cyclic structures needing an algebraic correction before reshaping can proceed.
The baseline is a strawman the authors had to build. The compared system explicitly assumes fusions never fail, so wrapping it in retry-until-success is the only way to compare at all. It is a fair construction and it is not a competitor that was designed for this setting.
Two hyperparameters are tuned by sweep. The ratio of module size to seam width peaks around seven, and the coarseness of the target grid is chosen as the smallest value where the success probability approaches one. Both come from sensitivity studies rather than analysis.
Photon loss is folded into the merge success probability as an effective reduction, which is a simplification of a physical process with its own structure.
There is no error correction here. This builds the entangled resource; a real machine needs a fault-tolerant code layered on top, which changes the resource accounting substantially and is out of scope.
Only two shapes of resource state were tested, four-qubit and seven-qubit star-like ones, and the tolerance floor for the merge success rate is 0.66 — comfortably below the practical 0.75, but not by a wide margin.

The evaluation

Coping with a merge that fails a quarter of the time

Property	Plan and retry, at an optimistic 90 percent	Plan and retry, at a realistic 75 percent
Hardware cycles for a four-qubit program
Merges used on a four-qubit program	Fewer — only what the program needs
Largest program demonstrated	Four qubits before the cycle count becomes unmeasurable
Whether merges can run concurrently	No — each retry depends on the last outcome
What the structure costs	Exactly the program graph, when it works	Unbounded, because restarts are unbounded

Four benchmark families — an optimisation ansatz, a Fourier transform, a ripple-carry adder and a variational eigensolver — from 4 to 100 qubits, simulated against a photonic architecture model with four-qubit and seven-qubit resource states.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The largest caveat is that the machine does not exist: this is a simulation against an architectural model, with timings drawn from a vendor roadmap for hardware still being built. Within that model, two things deserve care. The first is that the entire design is justified by a hard real-time budget — roughly five thousand nanosecond cycles before the photons are gone — and the paper never establishes that its real-time work fits inside it. The reported online timings are comparative, from a Python implementation, showing that the modular scheme is faster than the non-modular one; there is no absolute claim that connectivity checks and path searches across a layer of hundreds of thousands of qubits complete in microseconds. The second is the classical memory: 192 gigabytes during execution for a 64-qubit program, brought down by a periodic flush that costs 13 to 19 percent more cycles. The paper is honest about where it loses — on four-qubit programs it uses between roughly 1.5 and 20 times more merges than the baseline, because a fixed pattern fires everything whether needed or not — and about what modularity costs, roughly 40 percent of the grid an unrestricted search would find. The clean percolation argument holds for a plain square lattice; the real construction merges layers to raise connectivity and those merges fail into tangled structures needing algebraic cleanup. The comparison baseline was assembled by the authors from a system that assumes failures never happen, which is fair given that nothing else exists and is not a contest between designs built for the same problem. And this is resource construction only — a fault-tolerant machine needs error correction on top, which would change the accounting entirely.

Background

Why photonics computes differently from everything else

The reason this platform needs its own compiler stack comes down to a single physical fact: photons barely interact with one another. That is a gift for coherence — a photon flying down a fibre is not disturbed by its neighbours, which is why these qubits keep their state for so long and integrate naturally with optical networks. It is also what makes a two-qubit gate, the thing every circuit-model compiler is built around, extremely awkward to construct. So the platform uses a different computational model entirely, one where all the entanglement is created up front and the computation is nothing but a carefully ordered sequence of single-qubit measurements. That inversion is total: what a circuit compiler thinks of as a gate becomes an edge in a graph, scheduling becomes graph embedding, and the hard problem becomes building a particular entangled structure rather than sequencing operations on a fixed set of qubits. It is a good illustration of how much of a toolchain is downstream of an abstraction choice, which is the same observation the Pauli-string compiler work covered elsewhere on this site makes from the other direction, arguing that once a quantum program has been flattened into gates, the compiler can no longer see the structure that would have told it what is safe to rearrange. Here the structure being preserved is the graph, and the entire framework exists to keep it visible from the program all the way down to the photons.

If you remember only three things

1. Photonic quantum computers are assembled by an operation that succeeds about 75 percent of the time and destroys both photons when it fails, so the entangled structure you get is never the one you planned — and repairing it is serial, sometimes impossible, and races a clock set by photons decaying in fibre after roughly five thousand cycles.
2. OnePerc stops specifying the shape and specifies a statistical property instead: fire every merge concurrently in a program-agnostic pattern, and rely on percolation — above a threshold of one half, and the achievable rate is three quarters, a randomly connected grid almost certainly contains one giant component — then carve a regular lattice out of that component by finding non-touching crossing paths, since unwanted qubits can be measured away for free.
3. The hard deadline forces every judgement offline, so an intermediate representation stands between the halves: the real-time pass promises a stack of fixed-size grids with individually switchable edges, which is far more regular than the hardware and strictly within what reshaping can deliver — letting ordinary mapping algorithms target something deterministic, and taking programs from four qubits at an optimistic success rate to a hundred at a realistic one.

Check yourself

Check your understanding

1. Why does retrying failed merges not scale?
2. What does percolation contribute to the design?
3. Why is the reshaping target program-agnostic?
4. Which limitation most affects how the results should be read?

Sources

The paper is “OnePerc: A Randomness-aware Compiler for Photonic Quantum Computing” by Hezi Zhang, Jixuan Ruan, Hassan Shapourian, Ramana Rao Kompella and Yufei Ding, published at ASPLOS 2024, pages 738-754, DOI 10.1145/3620666.3651372. The authors are at the University of California San Diego and Cisco Research.

This explainer is written from the full arXiv text, arXiv:2403.01829. Everything above comes from the paper’s own sections: the background on measurement-based quantum computing, the translation from circuits to graph states, and the photonic hardware model with its periodic resource state generation, spatial and temporal routing, delay lines and photon lifetime; the survey of fusion success probabilities and the cost in auxiliary photons of raising them; the motivating example showing why adding retries to the prior compiler fails, including the two unrecoverable failure modes and the three critical issues it exposes; the fusion strategy covering sufficient and insufficient node degrees, the merging of layers to raise degree, the cyclic structures that failed degree-raising merges produce, the local complementation identity that removes them, the two theorems allowing that correction to be deferred past measurements and fusions, and the batched collective feed-forward; the reshaping design covering two-dimensional renormalisation with its path search, its percolation justification and its modular decomposition with the module-to-interval ratio, and the flexible time-like connections distinguishing logical from routing layers; the offline pass covering the virtual hardware abstraction and its three defining properties, the intermediate representation and mapping with its dynamic scheduling, occupancy cap and refresh mechanism, and the intermediate-level instruction set; and the evaluation covering the benchmark programs and hardware sizes, the comparison against the retry-based baseline in both cycles and fusion count at two success rates, the effect of the refresh mechanism under a memory limit, and the sensitivity studies on resource state size, hardware size, fusion success probability, modularity overhead, compilation time and the two hyperparameters.