Computação quântica sem colapso e problemas de conhecimento zero

Abstract

Resumo: A classe de problemas para os quais existem algoritmos quânticos eficientes é denotada por BQP (Bounded-error Quantum Polynomial). Uma abordagem comum em teoria da computação para a compreensão dos limites de uma classe de complexidade é esclarecer relações desta com outras subclasses e superclasses próximas. Uma superclasse de BQP que tem sido foco de pesquisa recentemente é a classe naCQP (non-adaptive Collapse-free Quantum Polynomial Time), também conhecida como PDQP (Product Dynamical Quantum Polynomial time), introduzida por Aaronson et al. (2016), a qual corresponde a problemas que podem ser resolvidos eficientemente por um algoritmo quântico em um modelo hipotético de computação em que é possível realizar medições sem provocar o colapso do estado quântico. Provas interativas de conhecimento zero têm recebido muita atenção nas últimas décadas, em virtude de suas aplicações importantes em segurança de informação. A classe dos problemas que admitem provas interativas de conhecimento zero estatístico na computação clássica é a classe SZK (Statistical Zero Knowledge). Embora a relação entre BQP e SZK ainda seja desconhecida, Aaronson et al. (2016) mostraram que SZK está contida em naCQP. Uma das abordagens para investigação de separações entre classes é o estudo de suas relações relativas a um oráculo. Aaronson et al. (2016) mostraram que existe um oráculo A para o qual NPA ^ naCQPA. Nós provamos que existe um oráculo A para o qual PA = BQPa = SZKA = naCQPA ã (UP n coUP)A = EXPA, onde UP (Unambiguous Polynomial time) é uma subclasse importante de NP. Ainda, mostramos que, relativo a um oráculo A escolhido uniformemente de modo aleatório, temos (UP n coUP)A ^ naCQPA com probabilidade 1. Nossos resultados ampliam resultados de Bennett et al. (1997), Fortnow e Rogers (1999), Tamon e Yamakami (2001) e Aaronson et al. (2016). A classe SZK possui muitas subclasses notáveis, como NISZK e NIPZKi. A classe NISZK é associada a sistemas de prova com somente um envio de mensagem do provador para o verificador. Para NIPZK1, subclasse de NISZK, ainda é requirido conhecimento zero perfeito e que as instâncias positivas do problema sejam aceitas pelo verificador com probabilidade igual a 1. Mostramos um problema completo para NIPZK1 e também que uma restrição não trivial do problema de subgrupo oculto está em NIPZK1. Além disso, mostramos uma restrição não trivial de um problema completo para NISZK que está em BQP.

Abstract: The class of problems for which there are efficient quantum algorithms is denoted by BQP (Bounded-error Quantum Polynomial). A common approach in theoretical computer science to understand the limitations of a complexity class is to clarify its relationships with other nearby subclasses and superclasses. A superclass of BQP that has been the focus of research recently is the class naCQP (non-adaptive Collapse-free Quantum Polynomial Time), also known as PDQP (Product Dynamical Quantum Polynomial time), introduced by Aaronson et al. (2016), which corresponds to problems that can be solved efficiently by a quantum algorithm in a nonadaptive computing model where measurements can be made without causing the quantum state to collapse. Interactive statistical zero-knowledge proofs have received much attention in recent decades because of their important applications to information security. The class of problems that admit statistical zero-knowledge interactive proofs in classical computing is the class SZK (Statistical Zero Knowledge). Although the relationship between BQP and SZK is still unknown, Aaronson et al. (2016) have shown that SZK is contained in naCQP. A common approach for investigating separation between classes is the study of their relations relative to an oracle. Aaronson et al. (2016) showed that there is an oracle A for which NPA ^ naCQPA. We prove that there exists an oracle A for which PA = BQPA = SZKA = naCQPA # (UP n coUP)A = EXPA, where UP (Unambiguous Polynomial time) is an important subclass of NP. Furthermore, we show that for an oracle A chosen uniformly at random, we have (UP n coUP)A ^ naCQPA with probability 1. Our results extend results from Bennett et al. (1997), Fortnow e Rogers (1999), Tamon e Yamakami (2001) and Aaronson et al. (2016). The class SZK has many notable subclasses, such as NISZK and NIPZKi. The NISZK class is associated with proof systems with only one message sent from the prover to the verifier. For NIPZK1, a subclass of NISZK, we still require perfect zero knowledge and that the positive instances of the problem are accepted by the verifier with probability equal to one. We show a complete problem for NIPZK1 and also that a non-trivial restriction of the hidden subgroup problem is in NIPZK1. Furthermore, we show a non-trivial constraint of a complete problem for NISZK which is in BQP. Keywords: computational complexity. quantum computing. oracle separation.