Como o algoritmo Grover é aplicado a um banco de dados?

Questão

Eu quero usar o algoritmo Grover para pesquisar um banco de dados não classificado para um elemento . Agora, surge a pergunta: como inicializar o índice e o valor do banco de dados com os qubits?$x$

Exemplo

• Digamos que eu tenho qubits. Assim, valores clássicos podem ser mapeados.$4$$2 ^ 4 = 16$
• Meu banco de dados não classificado tem os seguintes elementos: .$d$$d [\text{Value}] = [3,2,0,1]$
• Eu quero procurar por .$x = 2_d = 10_b = |10\rangle$
• Minha abordagem: indexe o banco de dados $d$ com $d [(\text{Index, Value})] = [(0,3), (1,2), (2,0), (3,1)]$ . Registra $0$ e $1$ para o índice e registra $2$ e $3$ para o valor. Em seguida, aplique o algoritmo Grover apenas aos registros $2$ e $3 (\text{Value})$ . Isso pode ser realizado? Existe outra abordagem?

O que eu já implementei ( no GitHub )

O "algoritmo Grover com 2-, 3-, 4-Qubits", mas o que faz é simples: os bits são inicializados com $|0\rangle$ , o oracle marcará minha solução $x$ (que é apenas um número como $2_d = 10_b$ ), a parte Grover aumentará a probabilidade do elemento selecionado $x$ e diminuirá todas as outras probabilidades e, em seguida, os qubits serão lidos ao serem mapeados para os bits clássicos. Deixamos que esse processo fosse executado várias vezes sucessivamente e, assim, obtivemos uma distribuição de probabilidade, onde a maior probabilidade tem o elemento procurado $x$ .

A saída é sempre a mesma que a marcada no oráculo. Como posso gerar mais informações a partir da saída, que eu não sabia no momento em que construí o oráculo?

Eu tenho trabalhado nesse problema também. Como iniciante e programador clássico (ou seja, eu não falo Mecânica Quântica), é difícil entender os conceitos sem exemplos completos. Eu tenho trabalhado com o exemplo Microsoft Q # Database Search . Ele simplesmente procura por um índice / chave específico no banco de dados, o que não é muito útil. Eu expandi esse exemplo para pesquisar uma lista de valores em um banco de dados e retornar a chave correspondente.

Como no seu exemplo, há um "registro de chave" de dois qubit para os índices e um registro de dois qubit separado para os valores. Há também um quinto "qubit marcado" que vem da amostra da Microsoft, para indicar quando o valor desejado é encontrado. As chaves e os valores são associados via emaranhamento. Isso é melhor demonstrado com um circuito. Clique aqui para ver o circuito Quirk real .

Note que este circuito contém apenas o oráculo. Ele não implementa todo o algoritmo de Grover.

• Os dois qubits superiores são o registro de chaves, os dois seguintes são o registro de valores e o qubit inferior é o qubit marcado.
• A primeira seção coloca o registro de chaves em uma superposição uniforme usando portas Haramard, conforme exigido pelo algoritmo de Grover.
• A segunda seção é onde as chaves são associadas aos valores via emaranhamento. Cada chave é entrelaçada com um valor correspondente no registro de valores aplicando portas X (Anti) controladas. Portanto, quando o registro da chave for 0, o registro do valor será definido como 3. Quando a chave for 1, o valor será definido como 2 e assim por diante.
• A terceira seção do circuito é o oráculo de busca. O registro de valores está emaranhado com o qubit marcado. Neste exemplo, o valor desejado é 2. Quando o registro de valor contém 2, o qubit marcado será definido como 1.
• O algoritmo de Grover analisa o registro de chaves e o qubit marcado. O oracle de pesquisa examina o registro de valores e define o qubit marcado. Isso fará com que a chave 1 seja amplificada quando o valor for 2.

É interessante notar que as chaves e os valores não são armazenados nos qubits, mas no circuito / programa. Você poderia dizer que não é realmente um banco de dados em si. É mais como uma instrução switch / case, mas que pode ser executada com uma superposição de valores.

Para mais detalhes, advertências e código Q #, consulte meu repositório GitHub .

EDIT: Algo que eu entendo melhor desde a resposta ... você precisa reverter / desfazer o circuito como parte de cada iteração. No código Q #, a chamada Adjoint StatePreparationOracle () na operação ReflectStart () lida com isso, portanto, não precisei fazer isso explicitamente. Não sei se o Qiskit tem um recurso semelhante. Se eu fiz a tradução corretamente, aqui está um circuito completo para o exemplo acima.

Ao apresentar o algoritmo de Grover aplicado à pesquisa em um banco de dados, supõe-se que o Oracle tenha acesso aos elementos da lista clássica. No entanto, é uma suposição muito forte e é por isso que representamos isso por um seletor controlado usando CNOT / Toffolis de um índice que representa simplesmente essa operação (como o circuito de Toffoli no caso ).$n=4$

Você mencionou a abordagem de calcular os valores em outro registro: Você assume novamente que recebe um oráculo para fazê-lo e de forma eficiente (uma maneira direta é controlar - NÃO, mas você deve fazer isso para todos os índices / valores, para que não sejam muito eficientes). Nesse caso, o oráculo seria a função em um formato de circuito quântico (novamente um seletor controlado), marcando esse estado e continuando com as iterações de Grover.

Eu acho que é melhor pensar no algoritmo de busca quântica como otimizando uma função, em vez de procurar em uma lista / banco de dados. Aqui está um artigo em que trabalhei sobre onde a pesquisa quântica é usada para resolver um problema de maximização combinatória, se você deseja aprofundar sua compreensão do algoritmo.

Você precisa converter o oracle para manter o banco de dados também; como resultado, o Oracle geral (Phase Inversion) terá dois sub oráculos para dar uma olhada na figura.

O primeiro sub oráculo que precisa ser preparado é o circuito de memória, em contraste com o QRAM que armazena dados quânticos (estado) em seu corpo, esse circuito de memória (array) está preparado para armazenar apenas informações clássicas em seu quadro. Um exemplo desse tipo de circuito que armazena uma matriz de binários [010, 110, 100, 011] é exibido abaixo: Para mais, leia este documento .