Open gwwatkin opened 3 years ago
@alexandrupaler drawing of the comparison. We looked at the idea by trying the example of a Toffoli gate:
Trying to sum up @alexandrupaler's discussion: The essential idea is that on the fly parallelization might be more effective in Horseman's formalism. Optimizing Litinski's Pauli rotations becomes a combinatorial problem that could be hard to solve on the fly. On the other hand some circuits (like potentially the Toffoli gate in the example) naturally fall into a parallelizeable configuration.
Targets
Litinski Compilation: The one we've been following so far: goes through pauli rotations and multibody measurement with ancilla regions (for which the details of the stabilizer measurements are not 100% clear yet). Includes the stabilizer commuting transform.
Via ZX: #116
Horsman Compilation: based on the original lattice surgery paper, Horsman et al. 2013. Update 2021-11-14: The ZX approach might be more relevant now.
The first kind of compilation is the one we already have. What we need to do next is implement operations as they are given by horseman et all. At least Pauli operations and CNOTs. Started add transversal ops in #91 and #93. For CNOTs, we are interested in the non transversal one in Horsman et al. so we need to find a way of expressing that too.
Benchmark circuits
We want to see with realistic circuits how these two compare.
Three levels of real world circuit to benchmark on (from less to more structured):
NISQ: algorithms like QAOA and VQE.
Intermediate: Quantum random walks, Quantum Neural Networks.
Structured: Oracles with arithmetic (eg. with Karatsuba multipliers), Shor's.
Simulation and corrective terms
A the moment we are simulating states to obtain corrective terms that follow multibody measurements (Litinski, sec 1.1). It probably is desirable to run some tests without simulation. We could extrapolate from a small scale example the frequency of these terms and then apply them randomly; alternatively consider the worst case and always apply them.