Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries

A quantum random access memory lets a quantum computer look up data at many addresses at once, in superposition, and the leading design routes each query down a binary tree of quantum switches — but that tree has a single entrance at its root, so every query must pass through it one at a time, and a shared memory serving many processors becomes a bottleneck; this paper (Yale) borrows the classical fat-tree network idea, thickening the tree near the root with duplicated switches, so that logarithmically many independent queries can be pipelined through at once in the same time and qubit budget, cutting circuit depth for parallel quantum algorithms by up to a factor of ten.

The argument in one glance

Problem

A quantum memory that reads many addresses at once, but only one query at a time

Many of the quantum algorithms that promise real advantage — for chemistry simulation, for solving linear systems, for factoring — assume they can query a large memory in superposition: ask for many addresses at once and get back a superposition of the stored values. The device that provides this is a quantum random access memory, and the leading design, bucket-brigade QRAM, does it by sending a query down a tree of quantum switches, one switch per node, reaching the data at the leaves. For a single query this is excellent: it finishes in time and error that grow only logarithmically with the memory size, using a number of qubits proportional to the memory. But the tree has one entrance, its root, and a query occupies that root — and in fact the whole tree — for its entire duration. So a second query cannot even begin until the first is completely done. The memory can serve only one query at a time.
What people did

Share the one bucket-brigade memory and queue the queries

When several quantum processors, or a parallel algorithm issuing many queries, want to use a shared QRAM, the natural thing is to let them all target one bucket-brigade memory and queue their queries, running them one after another down the same tree.
Why it fell short

Serializing queries makes a shared memory a bottleneck

Because a bucket-brigade query holds the root and the entire tree from start to finish, queuing means strict serialization: with several processes contending, the total latency grows in proportion to the number of queries times the logarithmic cost of each. Most of the tree sits idle at any instant — only the routers along one root-to-leaf path are doing anything — yet none of that idle hardware can be used by another query. For parallel quantum algorithms whose whole point is to issue many queries at once, this lack of query-level parallelism erases the benefit and turns the shared memory into a bottleneck.
This paper's idea

Thicken the tree near the root, like a classical fat-tree, and pipeline queries

Fat-Tree QRAM reorganizes the quantum routers the way a classical fat-tree network does: it duplicates the routers near the root, where contention is worst, and thins the duplication toward the leaves, so the tree is fat at the top and matches an ordinary bucket-brigade tree at the bottom. This extra bandwidth near the root lets logarithmically many independent queries be pipelined through the memory at once, finishing in the same logarithmic time and using the same order of qubits as one bucket-brigade query, while keeping essentially the same fidelity.

Why this problem is worth solving

The device at issue is unusual: it is a memory whose entire purpose is to be addressed in superposition.

A quantum random access memory, or QRAM, performs a query that reads memory at many addresses simultaneously in superposition. Given an input register holding a superposition of addresses, it returns a superposition in which each address is paired with the classical value stored there, all in one operation. This is what lets quantum algorithms load large datasets or large tables of precomputed values without destroying the superposition they compute on, and it is a required ingredient for algorithms in quantum chemistry, quantum machine learning, and cryptography. The leading realization is bucket-brigade QRAM, which arranges quantum routers — small switches, each built from controlled-swap gates — in a binary tree, with the classical data at the leaves. A query walks address information down the tree, activating one path per address in the superposition, and reads the data back out. Its appeal is that both the time and the error of a query grow only logarithmically or poly-logarithmically with the memory size, and it is unusually robust to noise, which makes it a leading candidate even before full fault tolerance.

The reason a single memory becomes a system bottleneck is that quantum computing is increasingly about running things in parallel and sharing scarce hardware.

In a shared memory system, several quantum processing units draw on one QRAM to improve utilization of an expensive resource, exactly as cores share memory in a classical machine. The rate at which such a memory can satisfy queries is its bandwidth, and bandwidth is what parallel workloads need. Two trends make this pressing: quantum hardware is moving toward modular designs where many small units are linked into one machine, and a growing family of parallel quantum algorithms — parallel versions of quantum signal processing, quantum walks, phase estimation, and distributed eigensolvers — succeed only if a high-bandwidth memory can serve their simultaneous queries. A memory that can answer only one query at a time has, in effect, a bandwidth that shrinks as the memory grows, because each query takes logarithmically longer. Raising QRAM bandwidth so that many queries proceed at once, without paying more qubits or losing fidelity, is therefore what turns these parallel algorithms and shared-memory designs from paper proposals into practical ones.

What people did before, and where it broke

Bucket-brigade QRAM for a single query. Route a query down a binary tree of quantum routers, reaching data at the leaves in logarithmic time with strong noise resilience. Where it broke. It is built for one query at a time; the root is the sole entrance and the query holds the whole tree for its full duration, so nothing else can run concurrently.
Share one bucket-brigade memory and queue. Let many processors target the same tree and serialize their queries. Where it broke. Serialization makes total latency scale with the number of queries times the per-query logarithmic cost, and it wastes the tree, most of which is idle during any single query.
Duplicate the whole memory (a copy per query). Provide bandwidth by building several full bucket-brigade trees so queries run on separate copies. Where it broke. This achieves constant bandwidth only by paying a logarithmic number of complete hardware copies — many times the qubits — which is prohibitively expensive for a large memory.
Virtual or time-sliced sharing. Manage a single memory more cleverly to interleave access. Where it broke. Without extra bandwidth where queries actually contend — at the root — interleaving still cannot get more than one query through the single entrance at a time, so it does not deliver true query parallelism at an acceptable space-time cost.
The gap. No design let many independent queries flow through one QRAM at once while keeping the same order of qubits and the same logarithmic time and fidelity as a single bucket-brigade query. What was missing was a way to add just enough bandwidth exactly where queries collide, near the root, without duplicating the entire, leaf-heavy tree.

How Fat-Tree QRAM is built

Thickening a bucket-brigade tree into a fat-tree for pipelined queries

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

The idea

Borrow the fat-tree: put the bandwidth where the traffic converges. The root of a binary tree is a chokepoint because every query must funnel through it, and a plain bucket-brigade tree gives the root exactly the same meager hardware as any other node — one router, one wire. Classical computer architects solved the identical problem for interconnection networks decades ago with the fat-tree, which makes the links thicker near the root, where all the traffic converges, and thinner near the leaves, where it fans out. Fat-Tree QRAM applies that geometry to quantum routers: it duplicates the routers near the root and tapers the duplication toward the leaves, so the tree is fat where queries collide and lean where they do not. Bringing a proven classical-interconnect idea — provisioning bandwidth in proportion to where traffic concentrates — onto quantum hardware is the same cross-over the superconducting-chip communication-highway work covered elsewhere on this site makes, importing a networking structure to relieve a routing bottleneck that a naive quantum layout would otherwise choke on.

Pipeline queries the way a processor pipelines instructions. Once the top of the tree can hold more than one query worth of state, the queries need not run one after another; they can overlap in stages, exactly like instructions moving through a processor pipeline. As the first query descends from the root toward the leaves, the routers it vacates near the root become free, and a second query can enter behind it, then a third, and so on, until a logarithmic number of independent queries are simultaneously in flight at different depths. The whole batch then completes in the same logarithmic time a single query would take, so the memory answers many queries in the time it used to answer one. Turning idle, momentarily-free hardware into throughput by overlapping independent operations rather than serializing them is the same utilization instinct the qubit-reuse work covered elsewhere on this site is built on, packing more useful work onto scarce quantum hardware that would otherwise sit waiting.

Keep the bucket-brigade virtues while paying only a modest overhead. The move only matters if it does not sacrifice what made bucket-brigade attractive: its logarithmic qubit count, its logarithmic time, and above all its noise resilience, whose error grows only with the square of the logarithm of the memory size. Fat-Tree QRAM is careful here. The duplication is heaviest near the root, but the root levels are tiny compared to the exponentially larger leaf levels, so the total qubit count stays proportional to the memory size — only a small constant factor more than bucket-brigade — rather than the full logarithmic-factor blow-up of copying the whole memory. The extra routers add only a small constant factor to the infidelity, from a few additional gates, and the design is worked out concretely for superconducting cavities with their real connectivity limits and for error-corrected operation. Adding capability to a quantum architecture while co-designing it against the actual device and its error behavior, so the theoretical scaling survives contact with hardware, is the same discipline the modular-chiplet quantum-error-correction co-design work covered elsewhere on this site follows, insisting that an architectural idea prove itself under realistic qubits and codes rather than only on paper.

Following a batch of queries through Fat-Tree QRAM

Pipelining independent queries down the fat-tree

A trace, from the paper, of how Fat-Tree QRAM overlaps several independent queries where a bucket-brigade memory would run them one at a time.

Step 1 of 5

The first query enters the fattened root

A query begins by loading its address information into the root, which now holds several router copies instead of one. It starts descending the tree level by level, activating a path toward the leaves, just as in a bucket-brigade query but through the duplicated top of the tree.

Each query still takes on the order of ten times the tree depth in elementary circuit layers to complete a full round trip.

Why it works

Bandwidth is added exactly where queries collide. Every query funnels through the root, but a plain tree gives the root no more hardware than a leaf → but a fat-tree duplicates routers near the root and tapers toward the leaves → so the chokepoint gets the capacity for several queries while the tree stays lean where it need not grow.
The fat part is cheap because the tree is leaf-heavy. Duplicating routers sounds expensive, but the root levels are exponentially smaller than the leaf levels → but the duplication is heaviest exactly at those tiny top levels and tapers to none at the leaves → so the total qubit count stays proportional to the memory size, a small constant factor over bucket-brigade.
Pipelining converts idle hardware into throughput. In a single bucket-brigade query almost the whole tree is idle at any instant → but query-level pipelining fills the vacated upper routers with following queries → so a logarithmic number of queries finish in the time of one, instead of latency growing with the number of queries.
The bucket-brigade fidelity survives. The design would be pointless if parallelism wrecked the noise resilience → but the extra routers add only a few gates, changing infidelity by a small constant factor → so the memory keeps the poly-logarithmic error scaling that made bucket-brigade attractive before fault tolerance.
It is buildable on real superconducting hardware. An abstract tree of routers could be impossible under real connectivity → but the paper realizes the multiplexed routers with superconducting cavities and native controlled-swap gates in both modular and on-chip forms → so the bandwidth becomes a concrete device, and its access rate and utilization can be scheduled to the optimum.

What it costs (trade-offs and scope)

It is a blueprint and analysis, not a fabricated device. The paper proposes modular and on-chip superconducting implementations and analyzes their performance and fidelity under realistic parameters, but it is an architectural design and evaluation, not an experimental demonstration of a working Fat-Tree QRAM; realizing the multiplexed routers and their wider connectivity at scale remains hardware work ahead.
The parallelism is bounded, and matched to logarithmic batches. Fat-Tree QRAM pipelines on the order of a logarithmic number of queries, not arbitrarily many; a workload wanting far more simultaneous queries than that would still saturate the memory, and the benefit is greatest for parallel algorithms and shared workloads whose query counts fit this regime.
There is a real, if modest, overhead. The design uses a constant factor more qubits than bucket-brigade and incurs a small constant-factor increase in infidelity from the additional gates, plus wider inter-node wiring and more complex routers; these are moderate, but they are not free, and they compound the already substantial resource cost of any large QRAM.
Throughput depends on the schedule and the workload balance. The gains assume the query-scheduling protocol keeps the pipeline full, which depends on how much independent processing each requesting processor does between queries; if queries arrive too sparsely or too bursty relative to processing, utilization falls short of the optimum the architecture allows.
QRAM’s ultimate usefulness is still algorithm-dependent. As the paper itself notes, QRAM does not help every algorithm — a merely quadratic speedup like unstructured search may not reach practical advantage — so higher QRAM bandwidth accelerates the algorithms that genuinely need superposition queries at scale, and is not a universal quantum speedup.

The evaluation

Serving parallel queries to a size-N quantum memory

Property	Bucket-brigade (shared)	Duplicated memories	Fat-Tree QRAM
Queries in flight at once
Qubit cost
Bandwidth versus memory size
Fidelity (query infidelity)		Same per copy
Parallel-algorithm circuit depth

From the paper's analysis. Fat-Tree QRAM attains a bandwidth and memory access rate independent of the memory size N and asymptotically less space-time volume per query than bucket-brigade or virtual QRAM, while duplicated memories reach constant bandwidth only by paying a logarithmic number of full hardware copies. The up-to-tenfold circuit-depth reduction is reported for parallel quantum algorithms at a memory of about a thousand entries.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is an architecture and a careful analysis, and it should be read that way. Fat-Tree QRAM cleanly solves the root-bottleneck of shared bucket-brigade memory by borrowing the classical fat-tree: duplicate routers near the root, taper toward the leaves, and pipeline a logarithmic number of independent queries through in one query’s worth of time, at only a constant-factor qubit overhead and a small constant-factor fidelity cost, with a bandwidth that no longer shrinks as the memory grows and up to a tenfold circuit-depth reduction for parallel algorithms. Read that with its scope in mind. This is a proposed design with modular and on-chip superconducting implementations analyzed under realistic parameters, not a built device, so fabrication at scale is future work. The parallelism is logarithmic, not unlimited, and the throughput depends on a scheduler keeping the pipeline full given each processor’s between-query processing. The overheads in qubits, wiring, and gates are moderate but real, and QRAM’s benefit is confined to algorithms that genuinely need large superposition queries. Within those bounds it is a compelling answer to a concrete question: how to give a shared quantum memory real bandwidth without paying for it in qubits or fidelity.

Background

Why a memory bottleneck matters for quantum computing

It helps to see why so much rides on the bandwidth of one component. Quantum computers are, and will long remain, painfully resource-constrained: qubits are few, expensive, and noisy, and the algorithms that promise advantage tend to demand enormous circuits with long coherence times. Two responses dominate the field’s roadmap. One is to run things in parallel — distributing an algorithm across processors, or issuing many independent operations at once — because parallelism trades scarce depth for breadth. The other is to share expensive hardware among many users and processes, as classical computing has always done, to keep utilization high. Both responses converge on the same requirement: a memory that many parties can query at once. A QRAM that can serve only one query at a time silently caps both strategies, forcing parallel algorithms back into serial query queues and making a shared memory a point of contention rather than a shared resource. That pressure, where scaling a quantum machine is as much about sharing and parallelizing scarce hardware as about adding qubits, is the same pressure the fault-tolerant million-qubit distributed-computer work covered elsewhere on this site is organized around, treating a large quantum computer as many modest units that must cooperate. Fat-Tree QRAM is a piece of that puzzle: it makes the shared memory keep up with the parallelism the rest of the machine is being designed to exploit.

If you remember only three things

1. Quantum algorithms for chemistry, machine learning, and factoring need a quantum random access memory that reads data in superposition, and the leading bucket-brigade design routes each query down a binary tree of quantum routers with good logarithmic time, qubit, and error scalings — but the tree has a single root entrance that a query holds for its whole duration, so queries must be serialized, and a shared memory or a parallel algorithm issuing many queries pays a latency that grows with the number of queries.
2. Fat-Tree QRAM borrows the classical fat-tree network: it duplicates the quantum routers near the root, where every query converges, and tapers the duplication to a single router at the leaves, widening the inter-node wiring to match; this adds bandwidth exactly at the chokepoint while keeping the total qubit count proportional to the memory size, because the fattened top levels are exponentially smaller than the leaf levels.
3. The extra bandwidth lets logarithmically many independent queries be pipelined through the memory at once — like instructions in a processor pipeline — finishing in the same logarithmic time as a single bucket-brigade query, with fidelity worse by only a small constant factor, a bandwidth independent of memory size, and up to a tenfold circuit-depth reduction for parallel quantum algorithms; the paper gives modular and on-chip superconducting-cavity implementations and a query-scheduling protocol, though it is an analyzed design rather than a built device.

Check yourself

Check your understanding

1. Why can a bucket-brigade QRAM only serve one query at a time?
2. What idea does Fat-Tree QRAM borrow from classical computing, and how does it apply it?
3. How does the fat-tree structure keep the qubit cost proportional to the memory size?
4. What does Fat-Tree QRAM achieve, and at what cost?

Sources

The paper is “Fat-Tree QRAM: A High-Bandwidth Shared Quantum Random Access Memory for Parallel Queries” by Shifan Xu, Alvin Lu, and Yongshan Ding (Yale Quantum Institute, Yale University), published at ASPLOS 2025 (Volume 2), DOI 10.1145/3676641.3716256.

This explainer is written from the full text of the authors’ arXiv version (arXiv:2502.06767). Everything above comes from the paper’s own sections: the introduction motivating high-bandwidth shared QRAM for parallel quantum algorithms (parallel quantum signal processing, quantum walks, phase estimation, distributed eigensolvers and Shor) and modular quantum hardware; the background on quantum queries and bucket-brigade QRAM (its quantum-router building block of controlled-swap gates in a wait, route-left, or route-right state, the binary-tree organization, the three-stage query of address loading, data retrieval, and address unloading, the logarithmic time and qubit scalings, and the infidelity bound growing with the square of the logarithm of the memory size); the challenges section explaining that the single root entrance forces serialization and a latency growing with the number of queries; the Fat-Tree architecture (level i nodes duplicated so a node holds a number of routers decreasing with depth, the three-tuple router indexing, and inter-node wiring widening from the root to a single wire at the leaves, with total qubits remaining proportional to the memory size); the modular and on-chip superconducting-cavity implementations with native controlled-swap gates under realistic connectivity; the query-scheduling and pipelining protocol and the query timing (about ten times the tree depth in circuit layers per query plus processing); and the evaluation introducing bandwidth, space-time (quantum) volume per query, hardware utilization, and memory access rate as metrics, showing Fat-Tree QRAM’s bandwidth and access rate independent of memory size and asymptotically lower space-time volume than bucket-brigade and virtual QRAM, the up-to-tenfold circuit-depth reduction for parallel algorithms at a memory of about a thousand entries, the small constant-factor infidelity difference from bucket-brigade, and the discussion of error-corrected queries.