Part of: A Series of Unfortunate Assumptions
In the design of quantum algorithms and circuits, there are a ton of tradeoffs to be made, at large and small scales. For example, a subroutine might have several reasonable implementations, each of which have different ancilla and gate costs. At a higher level, certain algorithmic choices are more amenable to low-depth or low-space implementations.
Thus, algorithm and circuit designers have to make heuristic decisions about how to balance cost metrics. Is it worth it to save X number of gates at the cost of Y extra ancillas? These heuristic decisions are typically made with a computational architecture in mind.
For the past several years, I have worked under the heuristic that you should do everything you can to minimize logical qubit count, even at the cost of moderately more gates. I was explaining this to someone recently and they told me I had been “surface code pilled.”
So what’s the story?
For years, it seemed likely that the first demonstrations of large-scale quantum algorithms would be performed on a device built out of superconducting qubits, with error correction performed via the surface code. As a broad statement, this architecture tends to have the following features:
- Many (perhaps ~500) physical qubits needed per logical qubit
- Fast cycle time
- Logical parallelism requires a lot of space
Here it makes sense to focus on minimizing the logical qubit count of the algorithm, even if it means a logical circuit with more gates and depth. Because parallelism is expensive and the cycle time is fast anyway, it’s not as important to come up with circuits that are parallel at the logical level—they would probably have to be executed sequentially anyway.
On the other hand, excitement has been growing about the prospect of neutral atoms with low-rate qLDPC codes. That architecture looks pretty dramatically different:
- Few (perhaps ~20) physical qubits needed per logical qubit
- Slow cycle time
- Logical parallelism is perhaps more achievable
The slow cycle time means that one of the primary difficulties is that the actual wall-clock time of computations can easily grow too long. See, for example, estimates of years of runtime to factor RSA-2048! Here, reducing circuit depth and gate count is potentially much more important.
Those years-long estimates for factoring are a great demonstration of the key point I want to make here: taking circuits that were developed for a superconducting qubit architecture, and putting them on an architecture they weren’t designed for, yields bad performance. If the algorithms had been designed from the ground up for this architecture, the runtime would be much shorter.
Many algorithmic and circuit design decisions over the past 10 years were made with surface codes and superconducting qubits in mind.
It’s crucial that we take a second look at old algorithms, and at the implementation choices made under the hood of new constructions, with new heuristics in mind!