14

^{Nota sobre o vocabulário: a palavra "hamiltoniano" é usada nesta pergunta para falar sobre matrizes eremitas.}

O algoritmo HHL parece ser um objeto ativo de pesquisa no campo da computação quântica, principalmente porque resolve um problema muito importante que é encontrar a solução de um sistema linear de equações.

De acordo com o artigo original, o algoritmo Quantum para resolver sistemas lineares de equações (Harrow, Hassidim & Lloyd, 2009) e algumas perguntas feitas neste site

Estimativa de fase quântica e algoritmo HHL - são necessários conhecimentos sobre autovalores?
Algoritmo quântico para sistemas lineares de equações (HHL09): Etapa 2 - Preparação dos estados iniciais e $\vert \Psi_0 \rangle$ $\vert b \rangle$

o algoritmo HHL é limitado a alguns casos específicos. Aqui está um resumo (que pode estar incompleto!) Das características do algoritmo HHL:

Algoritmo HHL

O algoritmo HHL resolve um sistema linear da equação com as seguintes limitações:

A | x ⟩ = | b ⟩

$A \vert x \rangle = \vert b \rangle$

Limitações em : $A$

precisa ser hermitiana (e apenas a matriz hermitiana funciona, vejaesta discussão no chat). $A$
autovalores de A precisam estar em (consulteEstimativa da fase quântica e algoritmo HHL - é necessário conhecimento sobre autovalores?) $A$ $[0,1)$
precisa ser eficiente implementável. No momento, as únicas matrizes conhecidas que satisfazem essa propriedade são:
- hamiltonianos locais (ver Universal Quantum Simulators (Lloyd, 1996) ).
- hamiltonianos separados (verGeração de estado quântico adiabático e conhecimento estatístico zero (Aharonov & Ta-Shma, 2003)). $s$

Limitações em : $\vert b \rangle$

deve ser eficiente preparável. É o caso de:
1. Expressões específicas de . Por exemplo, o estado $\vert b \rangle$ é eficientemente preparável. $| b ⟩ = ⨂_{i = 0}^{n} (\frac{| 0 ⟩ + | 1 ⟩}{\sqrt{2}})$ $\vert b \rangle = \bigotimes_{i=0}^{n} \left( \frac{\vert 0 \rangle + \vert 1 \rangle}{\sqrt{2}} \right)$
2. representando a discretização de uma distribuição de probabilidade eficientemente integrável (verCriando sobreposições que correspondem às distribuições de probabilidade eficientemente integráveis (Grover & Rudolph, 2002)). $\vert b \rangle$

Limitações em (saída): $\vert x \rangle$

não pode ser totalmente recuperado por medição. A única informação da qual podemos recuperar é um "informações gerais" ( "valor esperado" é o termo empregado no jornal HHL original) como $\vert x \rangle$ $\vert x \rangle$ $⟨ x | M | x ⟩$ $\langle x\vert M\vert x \rangle$

Pergunta: Levando em conta todas essas limitações e imaginando que estamos em 2050 (ou talvez em 2025, quem sabe?) Com chips quânticos de grande escala tolerantes a falhas (ou seja, não estamos limitados pelo hardware), que problemas do mundo real o algoritmo HHL poderia resolver (incluindo problemas nos quais o HHL é usado apenas como sub-rotina)?

Estou ciente do artigo Análise de recursos concretos do algoritmo do sistema linear quântico usado para calcular a seção transversal de espalhamento eletromagnético de um alvo 2D (Scherer, Valiron, Mau, Alexander, van den Berg & Chapuran, 2016) e da implementação correspondente em a linguagem de programação Quipper e estou procurando outros exemplos do mundo real nos quais o HHL seria aplicável na prática. Não preciso de um artigo publicado, nem mesmo um artigo não publicado, apenas quero ter alguns exemplos de casos de uso do mundo real .

EDITAR:

Mesmo se eu estiver interessado em todos os casos de uso, prefiro alguns exemplos em que o HHL é usado diretamente, ou seja, não usado como uma sub-rotina de outro algoritmo.

Estou ainda mais interessado em exemplos de sistemas lineares resultantes da discretização de um operador diferencial que poderia ser resolvido com HHL.

Mas deixe-me enfatizar mais uma vez que estou interessado em todos os casos de uso (sub-rotinas ou não) que você conhece .

algorithm hhl-algorithm applications Nelimee
fonte

Você mencionou que deseja alguns exemplos em que o HHL é "usado diretamente". Não sou muito claro sobre o que você quer dizer com isso. Conheço alguns algoritmos (que podem ter usos práticos) nos quais o HHL é uma das etapas principais, mas certamente não é a única . Algo como reconhecer sequências genéticas usando o HHL como uma das etapas principais (sujeita a todas as restrições que você mencionou) seria uma resposta adequada? Os outros passos primários envolvem principalmente simulação hamiltoniana e preparação do estado.

Sanchayan Dutta 11/07

Eu preferiria alguns exemplos em que o HHL é usado diretamente. Isso significa que o problema pode ser formulado diretamente como um sistema linear de equação a ser resolvido. É o caso da solução de equações diferenciais: discretizamos a equação e resolvemos o problema discretizado, que na maioria das vezes é um sistema linear esparso. Mas outros exemplos são bem-vindos.

Nelimee 11/07

5

Alguns anos atrás, foi mostrado nos algoritmos Quantum e no método dos elementos finitos por Montanaro e Pallister que o algoritmo HHL poderia ser aplicado ao Método dos Elementos Finitos (MEF), que é uma "técnica para encontrar eficientemente aproximações numéricas das soluções de valor-limite. problemas (BVPs) para equações diferenciais parciais, baseadas na discretização do espaço do parâmetro através de uma malha finita " .

Eles mostraram que, nesse contexto, o HHL poderia ser usado para obter (talvez no máximo) uma aceleração polinomial sobre o algoritmo clássico padrão (o "método do gradiente conjugado").

Com relação aos casos de uso do mundo real, eles afirmam que

$n$

$A$

SLesslyTall
fonte

2

M

$M$

M

$M$

s

$s$

s = 3

$s=3$

0

Rebentrost et al. recentemente utilizou o algoritmo HHL09 em seu artigo A Quantum Hopfield Neural Network (2018) , para otimizar a função de energia da rede Hopfield .

$E = -\frac{1}{2}x^{T}Wx + \theta^Tx$ $Px - x^{\text{(inc)}} = 0$ ) é:

L = - \frac{1}{2} x^{T} W x + θ^{T} x - λ^{T} (P x - x^{(inc)}) + \frac{γ}{2} x^{T} x

$\mathcal{L} = -\frac{1}{2}x^{T}Wx + \theta^Tx - \lambda^T (Px - x^{\text{(inc)}}) + \frac{\gamma}{2}x^T x$

\frac{\partial L}{\partial x} = 0

$\frac{\partial \mathcal{L}}{\partial x} = 0$

\frac{\partial L}{\partial λ} = 0

$\frac{\partial \mathcal{L}}{\partial \lambda} = 0$

A v = w

$A \mathbf{v} = \mathbf{w}$

γ

$\gamma$

v

$\mathbf{v}$

P x = x^{(inc)}

$Px = x^{(\text{inc})}$ e, portanto, precisamos de uma técnica de inversão matricial. No trabalho, eles fizeram exatamente isso e, para a inversão da matriz, utilizaram o algoritmo HHL09. Veja a página 4 do documento.

Em resumo, acredito que quando tivermos computadores quânticos com um número suficientemente grande de qubits e tempo de decoerência, o algoritmo HHL será uma das sub-rotinas mais úteis para qualquer algoritmo quântico de aprendizado de máquina (já que quase todo aprendizado de máquina e rede neural algoritmos envolvem alguma forma de "descida gradiente" ou "otimização").

Sanchayan Dutta
fonte

Quais poderiam ser as possíveis aplicações futuras para o algoritmo HHL?

Algoritmo HHL

Limitações em : $A$

Limitações em : $\vert b \rangle$

Limitações em (saída): $\vert x \rangle$

Respostas:

Quais poderiam ser as possíveis aplicações futuras para o algoritmo HHL?

Algoritmo HHL

Limitações em :AAA

Limitações em :|b⟩|b⟩\vert b \rangle

Limitações em (saída):|x⟩|x⟩\vert x \rangle

Respostas:

Limitações em : $A$

Limitações em : $\vert b \rangle$

Limitações em (saída): $\vert x \rangle$