check out the paper for more details!

cs.nyu.edu/~shw8119/25/...

Additionally, OAC outperforms existing quantum circuit optimizers, often producing a better quality final circuit in orders of magnitude less time.

In our experiments, we confirm that OAC performs strictly better than the naive chunked strategy, sometimes significantly so, removing thousands more gates from large circuit instances. This confirms that "melding" is important for circuit quality.

We call our algorithm OAC, for "optimize and compact".

We prove that this algorithm only calls the oracle productively: the number of additional calls to the oracle (due to melding, etc) is bounded by the number of optimizations found.

Melding can in turn expose even more opportunities for optimizations of individual chunks. So, after melding, we can continue optimizing recursively until convergence on a circuit which is (in some sense) "locally optimal" relative to the size-constrained oracle.

To address this, we develop a "melding" algorithm which identifies and performs additional optimizations across the boundaries.

But this immediately raises a question. Surely, this approach must miss optimizations that are possible across the boundaries between pieces, right?

(As you might expect, the answer is yes.)

thinking of these tools as black box optimizers or "oracles", a natural strategy would be to chunk up the circuit into small pieces and apply the oracle to each piece. This easily guarantees that the exponential searches are bounded and do not explode (in time/space)

the key challenge here is optimizing a large quantum circuit (with, e.g., hundreds of thousands of gates)

many existing tools are essentially superoptimizers, with exponential search spaces, and therefore can only handle "small" circuits in a reasonable amount of time/space

These days, you can buy such a machine for ~$3K. That’s a lot of compute per buck. Medium-scale parallelism is quite affordable

(“Medium scale” meaning large-ish single-node.)

I believe the idea (in ~2015) was: if you’re considering purchasing a car, consider spending your money on this 72-core 1TB multicore machine instead. They’re a similar price!

@anil.recoil.org might find this interesting!

for context, this slide is ~10 years old

When putting together the program, I noticed that there hadn’t been much CakeML at the ML Family Workshop, at least in the past decade.

Yong Kiam’s talk was excellent! 👏

I am endlessly impressed with CakeML — such an exciting project