Consideramos o problema de testar se um estado quântico n-qubit desconhecido é um estado estabilizador, com acesso a apenas uma cópia. Apresentamos um algoritmo que resolve esse problema utilizando O(n) cópias e, por outro lado, provamos que Ω(√n) cópias são necessárias para qualquer algoritmo. A principal observação por trás do nosso algoritmo é que, ao medir repetidamente em uma base de estabilizador escolhida aleatoriamente, os estados estabilizadores são os mais prováveis entre o conjunto de todos os estados puros de exibirem dependências lineares nos resultados das medições. Nosso algoritmo é projetado para investigar desvios desse comportamento extremo. Para a limitação inferior, primeiro reduzimos o teste de estabilizador à tarefa de distinguir estados estabilizadores aleatórios do estado maximamente misto. Em seguida, argumentamos que, sem perda de generalidade, é suficiente considerar estratégias de medição que a) estão no comutante da ação tensorial do grupo de Clifford e b) atendem a uma condição de Transposição Parcial Positiva (PPT). Ao aproveitar essas restrições, juntamente com resultados inovadores sobre as transposições parciais dos geradores do comutante de Clifford, derivamos a limitação inferior na complexidade da amostra.
Hinsche et al. (Qua,) estudaram essa questão.