Clifford circuits are an extremely well studied class of quantum circuits with a wide set of applications, such as error correction, quantum key distribution, learning theory, classical simulation, and more. Some well-known facts about Clifford circuits are that they generate the set of stabilizer states and that Clifford circuits with T gates form a universal gate set. Since stabilizer states were shown to be efficiently learnable by Montanaro in 2017 (as well as Aaronson and Gottesman in 2008), a major question in quantum learning was whether or not the same is true of states produced by Clifford circuits with a small number of T gates. To that end, we answer that question in the affirmative by giving a learning algorithm that runs in time poly(n)*exp(t) where n is the number of qubits and t is the number of T gates used. Along the way, we also give an efficient property tester for a magic monotone known as stabilizer nullity/dimension that runs in linear time in the number of qubits with no dependence on t. Both algorithms use Bell difference sampling as the main algorithmic tool.
Joint work with Sabee Grewal, Vishnu Iyer, and William Kretschmer
Copyright. All Rights Reserved.