| dc.description.abstract | One of the state of the art techniques for classically simulating quantum circuits relies on approximating the output state of the circuit by a superposition of stabilizer states.
If the number of non-Clifford gates in the circuit is small, such simulations can be very effective.
This thesis provides various improvements in this framework. First, we describe an improved method of computing approximate stabilizer decompositions, which reduces the time cost of computing a single term in the decomposition from $O(\ell n^2)$ to $O(m n^2)$, where $\ell$ is the total number of gates in the circuit, and $m$ is the number of non-Clifford gates.
Since this subroutine has to be repeated exponentially many times, this improvement can be significant in practice whenever $\ell \gg m$.
Our method uses a certain re-writing of the circuit, which in some cases allows for a significant amelioration of the exponential scaling of the required classical resources.
Furthermore, we describe a method of constructing exact, low-rank stabilizer decompositions of $\ket{\psi}^{\otimes m}$, where $\ket{\psi}$ is either a magic state or an equatorial state.
For any single qubit magic state $\ket{\psi}$, we find stabilizer decompositions of $\ket{\psi}^{\otimes m}$ with $2^{m\log_2(3)/4}$ terms. This improves on the best known bound of $2^{m \log_2(7)/6}$.
Similarly, for any single qubit equatorial state $\ket{\psi}$, we give a stabilizer decomposition of $\ket{\psi}^{\otimes m}$ with $2^{m/2}$ terms.
To our knowledge no such decompositions were previously known.
These results translate to milder exponential scaling of the classical resources required for estimating probabilities of quantum circuits up to a polynomially small multiplicative error, as well as allowing more types of circuits to be simulated in this way.
We also consider certain obstructions to classical simulations.
It has been argued in various contexts that contextuality and non-locality hamper classical simulations of quantum circuits.
Linear constraint systems (LCSs) are a generalization of the well-known Peres-Mermin magic square, which has been recently used to prove a separation between the power of constant depth classical and quantum circuits.
While binary LCSs have been studied in detail, $d$-ary LCSs are less well-understood. In this thesis we consider linear constraint systems modulo $d > 2$. We give a simple proof, of the previously known fact, that any linear constraint system which admits a quantum solution consisting of generalized Pauli observables in odd dimension must be classically satisfiable. We further prove that, for odd $d$, if a Pauli-like commutation relation between two variables in the LCS arises, then it has no quantum solutions in any dimensions, in stark contrast to the even $d$ case. We apply this result to various examples, for instance showing that many generalizations of the Peres-Mermin magic square do not give rise to a quantum vs. classical satisfiability gap. | en |
