Speaker
Description
The task of classically simulating quantum circuits is a particularly useful one, with applications including verifying the behaviour of quantum hardware and simulating quantum many-body problems. However, it is a notoriously difficult task to solve efficiently, as – for a logically complete gateset – the runtime complexity grows exponentially with the scale of the circuit. Recent literature has shown that representing quantum circuits in the graphical language of ZX-diagrams, and applying known decompositions of sets of computationally costly T-gates into sums of computationally cheap states, can allow circuits to be classically simulated in $O(2^{\alpha t})$ time, for some $\alpha < 1$.
In our work, we expand upon this by presenting a method by which a quantum circuit, expressed as a ZX-diagram, may be recursively partitioned into $k$ smaller counterparts which may each be computed independently at an exponentially reduced runtime. By appropriately cross-referencing the resulting scalars of computing these independent parts, one can arrive at a solution equivalent to having classically simulated the original circuit. By heuristically balancing the estimated costs of (a) computing the partitioned segments and (b) cross-referencing their results, we show how the partitioner can be automatically optimised to minimise the number of calculations required.
In benchmarking our method on randomly generated circuits, we show consistent improvements of many orders of magnitude versus the current state of the art ZX-decomposition approaches, particularly for deep circuits of relatively few qubits and shallow circuits of many qubits, as well as other circuits which inherently lend themselves to be efficiently partitioned. There is no upper limit to the improvement it can achieve, and experimentally we found many examples of circuits for which our method could compute in under one second what the best alternative approach would require an estimated years to complete.
