Halving the cost of QROM: Bringing meaningful algorithms closer to reality, now in PennyLane.

A new result from the Xanadu research team has effectively halved the best known cost of implementing QROM on quantum computers, the first major reduction in over half a decade.

This breakthrough result is available today in the development version of PennyLane as qre.SelectCopyQROM, allowing you to see this reduction immediately when implementing and analyzing your algorithms:

>>> import pennylane.labs.estimator_beta as qre
>>> qrom = qre.SelectCopyQROM(
...     num_bitstrings = 1e5,
...     size_bitstring = 32,
...     available_dirty_aux = 256,
... )
>>> print(qre.estimate(qrom))
--- Resources: ---
 Total wires: 311
   algorithmic wires: 49
   allocated wires: 262
     zero state: 262
     any state: 0
 Total gates : 1.922E+6
   'Toffoli': 1.659E+4,
   'CNOT': 1.831E+6,
   'X': 2.920E+4,
   'Hadamard': 4.448E+4

Read on to dive into the math behind this breakthrough, or start using it right away to optimize your algorithms.

Why is this so important?

QROM (quantum read-only memory) is the workhorse of most quantum algorithms, providing the essential mechanism for coherently accessing classical data on a quantum computer. Because of this, it often accounts for the majority of resource requirements across Hamiltonian simulation, state preparation, unitary synthesis, and quantum solvers for differential equations and linear systems.

Because of this ubiquity, any improvement in the quantum resources needed to implement QROM will have cascading effects throughout quantum algorithm development, bringing meaningful quantum algorithms closer to practical implementation.

This new methodology specifically reduces the number of Toffoli gates needed to implement QROM, effectively halving the required quantum cost, while also optimizing away redundant data-unloading steps when there are multiple back-to-back QROMs.

How does this work?

Naively, the coherent loading of N bitstrings of length b in superposition incurs a non-Clifford cost of N Toffolis. Previously, it was known through two papers [1] [2] that, given access to b (\lambda-1) dirty qubits, one can reduce the Toffoli cost of QROM to 2\frac{N}{\lambda} + 4b(\lambda - 1) using a SelectSwap architecture (as used in the existing qre.QROM resource operator).

In this work, the new QROM implementation introduces two primary structural improvements:

• SelectCopy architecture: By replacing the SelectSwap architecture with a SelectCopy one, the cost is reduced from 2\frac{N}{\lambda} + 4b(\lambda - 1) down to \,2\frac{N}{\lambda} + 2b(\lambda - 1) +2\lambda-6\, using the same b(\lambda-1) dirty auxiliary wire count.

• Removing redundant data-unloading: This allows m back-to-back QROMs (on different registers) with Toffoli cost (m+1)\left(\frac{N}{\lambda} + b(\lambda - 1) +\lambda-3\right).

Applying the above algorithm to the case of a single-table lookup (treating a single b-bit QROM as \alpha sequential \frac{b}{\alpha}-bit QROMs) achieves a Toffoli count of

yielding a parametric family of methods that interpolates the prefactor of the \frac{N}{\lambda} term between 2 to (1+\frac{1}{b}) (at the cost of increasing subleading terms).

The impact in practice

This decomposition is particularly useful in regimes of practical interest, where the number of available dirty qubits is limited and \frac{N}{\lambda} is the dominating term.

When N becomes large, \alpha = b becomes optimal (see the above figure). This yields a total cost of \sim (1+\frac{1}{b})\frac{N}{\lambda} instead of \sim 2\frac{N}{\lambda}, reducing the cost by approximately 50\% and effectively matching the performance of clean-qubit QROM using dirty qubits.

Will QROM get even cheaper?

We hope so! At Xanadu, we are constantly working across the stack to close the gap between theoretical breakthroughs and practical implementation. By integrating state-of-the-art resource reductions directly into our resource estimation tools, we ensure you can immediately benchmark and build upon these components the moment they are developed.

Stay tuned for more, and in the meantime subscribe to our newsletter, and follow PennyLane on LinkedIn or X/Twitter to stay in-the-loop on all the latest practical research breakthroughs.

• Paper: Halving the cost of QROM
• Documentation: qre.SelectCopyQROM
• PennyLane Labs: Access cutting-edge research tools with PennyLane Labs
• Learn more about QROM: Read our intro to quantum read-only memory and see how QROM can be used as a knob to trade between qubit and gate resources.