Optimality in Stabilizer Testing
Raja Oktovin Parhasian Damanik
Abstract:
Stabilizer states are important in quantum information, computation, and error correction. Stabilizer tester is a quantum algorithm that, given an access to several copies a quantum state, tests whether the state is a stabilizer state or far from it. It was an open question whether it is possible to obtain a stabilizer testing algorithm that is efficient and whose power is independent of the number of qubits. The question was answered in [GNW17] which provides a test that is perfectly complete, transversal, and independent of the number of qubits and only requires 6 copies of the state.
This thesis is about optimizing stabilizer testing. There are two main results in this thesis. The first is about stabilizer testing with few copies. We attempt to answer whether there exists a stabilizer testing algorithm that is perfectly complete and independent of the number of qubits given less than 6 copies of the state. We prove a no-go theorem for 4 copies; that it is not possible if the algorithm only has access to 4 copies. The second main result is about stabilizer testing with many copies. One run of the 6-copy stabilizer testing algorithm can give a type-II error with high probability. One can reduce the error by just repeating the 6-copy algorithm many times. We attempt to investigate whether there exists a protocol that is more efficient than the one that just repeats the 6-copy algorithm many times. The answer is affirmative.