26th Australian Institute of Physics Congress and the Australian and New Zealand Conference on Optics and Photonics

The Maximal Local Stabilizer Projector Problem and Applications in Classical Simulation of Clifford Plus T Circuits

Not scheduled

20m

Belinda Hutchinson Building (The University of Sydney )

Contributed Oral AIP | Quantum Science and Technology (QST)

Description

Our work forms two connected parts. The part-1 studies a class of computational problems associated with stabilizer states. The part-2 focuses on developing new state-of-the-art classical simulation algorithms.

Part-1: Stabilizer states are ubiquitous in quantum computing because they exhibit many important quantum properties such as superposition, entanglement and contextuality whilst also admitting compact classical representations that are computationally easy to manipulate. We characterize and study a class of natural optimization problems associated with stabilizer states. Specifically, we define a set of optimization problems where one is given an $n$ qubit stabilizer state $|\psi\rangle$ and a set of single qubit stabilizer projectors $S$ and one has the goal of projecting each qubit of $|\psi\rangle$ onto one of the projectors from $S$ in such a way that the 2-norm of the final state is maximized. Each choice of $S$ defines a different problem and we classify these into 9 distinct classes each with equivalent complexity. We show that two of these classes can be solved in polynomial time, 6 are NP-complete while the complexity of the last class is currently work in progress.

Part-2: We present a state-of-the-art classical simulation algorithm for Born rule probability estimation of $n$-qubit Clifford plus T circuits and show that its runtime
can be sped-up by a factor of $2^{-r}$ where $r\in \{0,1,\ldots,n\}$ is any upper bound on two of the (NP-complete) optimization problems from part 1. We empirically demonstrate that $r$ can be far from the trivial value of $0$ on large fraction of randomly sampled Clifford plus T circuits strongly motivating the search for efficient algorithms for finding non-trivial upper bounds. We present 3 efficient classical algorithms for computing non-trivial upper bounds to some of the relevant optimization problems. These are compared and the improvements to state-of-the-art classical simulation runtimes are empirically studied.