AplicaçõesApplications

Simulação HamiltonianaHamiltonian Simulation

A simulação dos sistemas quânticos é uma das aplicações mais excitantes da computação quântica.The simulation of quantum systems is one of the most exciting applications of quantum computation. Num computador clássico, a dificuldade em simular mecânica quântica, em geral, escala com a dimensão $N$ da sua representação de vetores de estado.On a classical computer, the difficulty of simulating quantum mechanics, in general, scales with the dimension $N$ of its state-vector representation. À medida que esta representação cresce exponencialmente com o número de qubits $n$ $N=2^n$, um traço conhecido também como a maldição da dimensionalidade,a simulação quântica no hardware clássico é intratável.As this representation grows exponentially with the number of $n$ qubits $N=2^n$, a trait known also known as the curse of dimensionality, quantum simulation on classical hardware is intractable.

No entanto, a situação pode ser muito diferente no hardware quântico.However, the situation can be very different on quantum hardware. A variação mais comum da simulação quântica é chamada o problema de simulação hamiltoniana independente do tempo.The most common variation of quantum simulation is called the time-independent Hamiltonian simulation problem. Lá, um é fornecido com uma descrição do sistema Hamiltonian $H$, que é uma matriz hermitiana, e algum estado quântico inicial $\ket{\psi(0)}} que é codificado em alguma base em $n$ qubits em um computador quântico.There, one is provided with a description of the system Hamiltonian $H$, which is a Hermitian matrix, and some initial quantum state $\ket{\psi(0)}$ that is encoded in some basis on $n$ qubits on a quantum computer. À medida que os estados quânticos em sistemas fechados evoluem sob a equação de Schrödinger $\ \begin{align} i\frac{d \ket{\psi(t)}}}}}}}}}}}}}}}}d} & = H\ket{\psi(t)}, \end{align} $$ O objetivo é implementar o operador unitário de evolução do tempo $U(t)=e^{-iHt}$ em algum momento fixo $t$, onde $\ket{\psi(t)}=U(t)\ket{\psi(0)}} resolve a equação de Schrödinger.As quantum states in closed systems evolve under the Schrödinger equation $$ \begin{align} i\frac{d \ket{\psi(t)}}{d t} & = H \ket{\psi(t)}, \end{align} $$ the goal is to implement the unitary time-evolution operator $U(t)=e^{-iHt}$ at some fixed time $t$, where $\ket{\psi(t)}=U(t)\ket{\psi(0)}$ solves the Schrödinger equation. Análogamente, o problema de simulação hamiltoniano dependente do tempo resolve a mesma equação, mas com $H(t)$ agora uma função do tempo.Analogously, the time-dependent Hamiltonian simulation problem solves the same equation, but with $H(t)$ now a function of time.

A simulação hamiltoniana é um dos principais componentes de muitos outros problemas de simulação quântica, e as soluções para o problema de simulação hamiltoniana são algoritmos que descrevem uma sequência de portões quânticos primitivos para sintetizar uma aproximação unitária $\tilde{U}$ com erro $ \ \tilde{U} - U(t) \ \ spectral normHamiltonian simulation is a major component of many other quantum simulation problems, and solutions to Hamiltonian simulation problem are algorithms that describes a sequence of primitive quantum gates for synthesizing an approximating unitary $\tilde{U}$ with error $\|\tilde{U} - U(t)\| \le \epsilon$ in the spectral norm. A complexidade destes algoritmos depende muito fortemente de como uma descrição do interesse hamiltoniano é acessível por um computador quântico.The complexity of these algorithms depend very strongly on how a description of the Hamiltonian of interest is made accessible by a quantum computer. Por exemplo, no pior dos casos, se $H$ agindo em $n$ qubits seriam fornecidos como uma lista de $2^n \times números de 2^n$ , um para cada elemento matricial, simplesmente ler os dados já exigiria tempo exponencial.For instance, in the worst-case, if $H$ acting on $n$ qubits were to be provided as a list of $2^n \times 2^n$ numbers, one for each matrix element, simply reading the data would already require exponential time. Na melhor das hipóteses, pode-se assumir o acesso a uma caixa preta unitária que $O\ket{t}ket{\psi(0)}*ket{t}U(t)\ket{\psi(0)}} trivialmente resolve o problema.In the best case, one could assume access to a black-box unitary that $O\ket{t}\ket{\psi(0)}=\ket{t}U(t)\ket{\psi(0)}$ trivially solves the problem. Nenhum destes modelos de entrada é particularmente interessante - o primeiro, uma vez que não é melhor do que abordagens clássicas, e este último como a caixa preta esconde a complexidade primitiva do portão da sua implementação, que poderia ser exponencial no número de qubits.Neither of these input models are particularly interesting -- the former as it is no better than classical approaches, and the latter as the black-box hides the primitive gate complexity of its implementation, which could be exponential in the number of qubits.

Descrições de HamiltoniansDescriptions of Hamiltonians

Por conseguinte, são necessários pressupostos adicionais do formato da entrada.Additional assumptions of the format of the input are therefore required. Deve ser alcançado um bom equilíbrio entre modelos de entrada suficientemente descritivos para abranger os hamiltonianos interessantes, como os de sistemas físicos realistas ou problemas computacionais interessantes, e modelos de entrada suficientemente restritivos para serem eficientemente implementáveis num computador quântico.A fine balance must be struck between input models that are sufficiently descriptive to encompass interesting Hamiltonians, such as those for realistic physical systems or interesting computational problems, and input models that are sufficiently restrictive to be efficiently implementable on a quantum computer. Uma variedade de modelos de entrada não triviais podem ser encontrados na literatura, e variam de quantum a clássico.A variety of non-trivial input model may be found in the literature, and they range from quantum to classical.

Como exemplos de modelos de entrada quântica, a simulação hamiltoniana baseada em amostras pressupõe o acesso à caixa preta para operações quânticas que produzem cópias de uma matriz de densidade $\rho$, que são consideradas a $H$.As examples of quantum input models, sample-based Hamiltonian simulation assumes black-box access to quantum operations that produce copies of a density matrix $\rho$, which are taken to be the Hamiltonian $H$. No modelo de acesso unitário supõe-se que o Hamiltonian, em vez disso, se decompõe numa soma de unitários $$ \start{align} H & = \sum^{d-1} _ {j=0} a _ j\hat{U} _ j, \end{align} $$ onde $a _ j>0$ são coeficientes, e $\hat{U} _ j$ são unidades.In the unitary access model one supposes that the Hamiltonian instead decomposes into a sum of unitaries $$ \begin{align} H & = \sum^{d-1}_{j=0} a_j \hat{U}_j, \end{align} $$ where $a_j>0$ are coefficients, and $\hat{U}_j$ are unitaries. Presume-se então que se tem acesso a caixa preta ao oráculo unitário $V=\sum^{d-1} _ {j=0}\ket{j}bra{j}\otimes \hat{U} _ j$ que seleciona o desejado $\hat{U} _ j$, e o oráculo $A\ket {0} =\sum^{d-1} _ {j=0}\sqrt{a _ j/\sum^{d-1} _ {k=0}alpha _ j}\ket{j}$ que criam um estado quântico codificando estes coeficientes.It is then assumed that one has black-box access to the unitary oracle $V=\sum^{d-1}_{j=0}\ket{j}\bra{j}\otimes \hat{U}_j$ that selects the desired $\hat{U}_j$, and the oracle $A\ket{0}=\sum^{d-1}_{j=0}\sqrt{a_j/\sum^{d-1}_{k=0}\alpha_j}\ket{j}$ that create a quantum state encoding these coefficients. No caso de simulação hamiltoniana escassa,assume-se que o Hamiltonian é uma matriz escassa com apenas $d=\mathcal{O}(\text{polylog}(N)$ elemento não-zero em cada linha.In the case of sparse Hamiltonian simulation, one assumes that the Hamiltonian is a sparse matrix with only $d=\mathcal{O}(\text{polylog}(N))$ non-zero element in every row. Além disso, assume-se a existência de circuitos quânticos eficientes que desloquem a localização destes elementos não nulos, bem como os seus valores.Moreover, one assumes the existence of efficient quantum circuits that output the location of these non-zero elements, as well as the their values. A complexidade dos algoritmos de simulação hamiltonianos é avaliada em termos de número de consultas a estas caixas negras, e a complexidade primitiva do portão depende muito da dificuldade de implementar estas caixas negras.The complexity of Hamiltonian simulation algorithms is evaluated in terms of number of queries to these black-boxes, and the primitive gate complexity then depends very much on the difficulty of implementing these black-boxes.

Nota

A notação big-O é comumente usada para descrever a complexidade do escalonamento de algoritmos.The big-O notation is commonly used to describe the complexity scaling of algorithms. Tendo em conta duas funções reais $f,g$, a expressão $g(x)=\mathcal{O}(f(x)$ significa que existe uma constante absolutamente positiva $x _ 0, c>0$ tal que $g(x) \le c f(x)$ para todos os $x\ge x _ 0$.Given two real functions $f,g$, the expression $g(x)=\mathcal{O}(f(x))$ means that there exists an absolute positive constant $x_0, c>0$ such that $g(x) \le c f(x)$ for all $x\ge x_0$.

Na maioria das aplicações práticas a implementar num computador quântico, estas caixas pretas devem ser eficientemente implementáveis, isto é, com portas quânticas primitivas $\mathcal{O}(\text{polylog}(N)$ portas quânticas primitivas.In most practical applications to be implemented on a quantum computer, these black-boxes must be efficiently implementable, that is with $\mathcal{O}(\text{polylog}(N))$ primitive quantum gates. Mais fortemente, os hamiltonianos eficientemente simuladores devem ter uma descrição clássica suficientemente escassa.More strongly, efficiently simulable Hamiltonians must have some sufficiently sparse classical description. Numa dessas formulações, presume-se que o Hamiltonian se decompõe numa soma de partes hermitianas $$ \start{align} H & = \sum^{d-1}__j=0} H_j.In one such formulation, it is assumed that the Hamiltonian decomposes into a sum of Hermitian parts $$ \begin{align} H & = \sum^{d-1}_{j=0} H_j. \end{align} $$ Além disso, presume-se que cada parte, uma $H _ hamiltoniana j$, é fácil de simular.\end{align} $$ Moreover, it is assumed that each part, a Hamiltonian $H_j$, is easy to simulate. Isto significa que o $e^{-iH _ j t}$ por qualquer momento $t$ pode ser implementado exatamente usando $\mathcal{O}(1)$ portões quânticos primitivos.This means that the unitary $e^{-iH_j t}$ for any time $t$ may be implemented exactly using $\mathcal{O}(1)$ primitive quantum gates. Por exemplo, isto é verdade no caso especial em que cada $H _ j$ são operadores locais da Pauli, o que significa que são de produtos tensores de operadores Pauli sem identidade que atuam em qubits espaciais próximos.For instance, this is true in the special case where each $H_j$ are local Pauli operators, meaning that they are of tensor products of $\mathcal{O}(1)$ non-identity Pauli operators that act on spatially close qubits. Este modelo é particularmente aplicável a sistemas físicos com interação limitada e local, uma vez que o número de termos é $d=\mathcal{O}(\text{polylog}(N)$, e pode claramente ser escrito, ou seja, clássicamente descrito, em tempo polinomial.This model is particularly applicable to physical systems with bounded and local interaction, as the number of terms is $d=\mathcal{O}(\text{polylog}(N))$, and may clearly be written down, i.e. classically described, in polynomial time.

Dica

Os hamiltonianos que se decompõem numa soma de peças podem ser descritos usando a biblioteca de representação do gerador dinâmico.Hamiltonians that decompose into a sum of parts may be described using the Dynamical Generator Representation library. Para mais informações, consulte a secção de Representação do Gerador Dinâmico nas estruturas de dados.For more information, see the Dynamical Generator Representation section in data structures.

Algoritmos de simulaçãoSimulation Algorithms

Um algoritmo de simulação quântica converte uma descrição dada de um Hamiltonian numa sequência de portões quânticos primitivos que, no seu conjunto, aproximam a evolução do tempo por dito Hamiltonian.A quantum simulation algorithm converts a given description of a Hamiltonian into a sequence of primitive quantum gates that, as a whole, approximate time-evolution by said Hamiltonian.

No caso especial em que o Hamiltonian se decompõe numa soma de partes hermitianas, a decomposição Trotter-Suzuki é um algoritmo particularmente simples e intuitivo para simular hamiltonianos que se decompõem numa soma de componentes eremitas.In the special case where the Hamiltonian decomposes into a sum of Hermitian parts, the Trotter-Suzuki decomposition is a particularly simple and intuitive algorithm for simulating Hamiltonians that decompose into a sum of Hermitian components. Por exemplo, um integrador de primeira ordem desta família aproxima -$ \start{align} U(t) & = \esquerda( e^{-iH _ 0 t / r} e^{-iH _ 1 t / r} \cdots e^{-iH _ {d-1} t / r} \right)^{r} + \mathcal{O}(d^2 \max_j \ H _ j \ [^2 t^2/r), \end{align} $$ usando um produto de $r d$ termos.For instance, a first-order integrator of this family approximates $$ \begin{align} U(t) & = \left( e^{-iH_0 t / r} e^{-iH_1 t / r} \cdots e^{-iH_{d-1} t / r} \right)^{r} + \mathcal{O}(d^2 \max_j\|H_j\|^2 t^2/r), \end{align} $$ using a product of $r d$ terms.

Dica

As aplicações do algoritmo de simulação Trotter-Suzuki estão cobertas nas amostras.Applications of the Trotter-Suzuki simulation algorithm are covered in the samples. Para o modelo Ising utilizando apenas as operações intrínsecas fornecidas por cada máquina-alvo, consulte a amostra SimpleIsing.For the Ising model using only the intrinsic operations provided by each target machine, please see the SimpleIsing sample. Para o modelo Ising utilizando a estrutura de controlo da biblioteca Trotter-Suzuki, consulte a amostra isingTrotter.For the Ising model using the Trotter-Suzuki library control structure, please see the IsingTrotter sample. Para hidrogénio molecular utilizando a estrutura de controlo da biblioteca Trotter-Suzuki, consulte a amostra de simulação H2.For molecular Hydrogen using the Trotter-Suzuki library control structure, please see the H2 simulation sample.

Em muitos casos, gostaríamos de implementar o algoritmo de simulação, mas não estamos interessados nos detalhes da sua implementação.In many cases, we would like to implement the simulation algorithm, but are not interested in the details of its implementation. Por exemplo, o integrador de segunda ordem aproxima -$ \start{align} U(t) & = \esquerda (e^{-iH _ 0 t / 2r} e^{-iH _ 1 t / 2r} \cdots e^{-iH _ {d-1} t / 2r} e^{-iH _ {d-1} t / 2r} \cdots e^{-iH _ 1 t / 2r} e^{-iH _ 0 t / 2r} \right)^{r} + \mathcal{O}(d^3 \max_j \ / H _ j \ [^3 t^3/r^2), \end{align} $$ usando um produto de termos de $2º$For instance, the second-order integrator approximates $$ \begin{align} U(t) & = \left( e^{-iH_0 t / 2r} e^{-iH_1 t / 2r} \cdots e^{-iH_{d-1} t / 2r} e^{-iH_{d-1} t / 2r} \cdots e^{-iH_1 t / 2r} e^{-iH_0 t / 2r} \right)^{r} + \mathcal{O}(d^3 \max_j\|H_j\|^3 t^3/r^2), \end{align} $$ using a product of $2rd$ terms. Encomendas maiores envolverão ainda mais termos e variantes otimizadas podem exigir encomendas altamente não triviais nos exponencials.Larger orders will involve even more terms and optimized variants may require highly non-trivial orderings on the exponentials. Outros algoritmos avançados também podem envolver o uso de qubits de ancilla em passos intermédios.Other advanced algorithms may also involve the use of ancilla qubits in intermediate steps. Assim, embalamos algoritmos de simulação no cânone como o tipo definido pelo utilizadorThus we package simulation algorithms in the canon as the user-defined type

newtype SimulationAlgorithm = ((Double, EvolutionGenerator, Qubit[]) => Unit is Adj + Ctl);

O primeiro parâmetro Double é o tempo de simulação, o segundo parâmetro , coberto na secção de EvolutionGenerator Representação do Gerador Dinâmico das estruturas de dados, é uma descrição clássica de um hamiltoniano independente do tempo embalado com instruções sobre como cada termo no Hamiltonian pode ser simulado por um circuito quântico.The first parameter Double is the time of simulation, the second parameter EvolutionGenerator, covered in the Dynamical Generator Representation section of data-structures, is a classical description of a time-independent Hamiltonian packaged with instructions on how each term in the Hamiltonian may be simulated by a quantum circuit. Os tipos deste formulário aproximam a operação unitária $e^{-iHt}$ no terceiro parâmetro Qubit[] , que é o registo que armazena o estado quântico do sistema simulado.Types of this form approximate the unitary operation $e^{-iHt}$ on the third parameter Qubit[], which is the register storing the quantum state of the simulated system. Da mesma forma para o caso dependente do tempo, definimos um tipo definido pelo utilizador com um EvolutionSchedule tipo, que é uma descrição clássica de um Hamiltonian dependente do tempo.Similarly for the time-dependent case, we define a user-defined type with an EvolutionSchedule type instead, which is a classical description of a time-dependent Hamiltonian.

newtype TimeDependentSimulationAlgorithm = ((Double, EvolutionSchedule, Qubit[]) => Unit : Adjoint, Controlled);

A título de exemplo, a decomposição Trotter-Suzuki pode ser chamada utilizando as seguintes funções canónicas, com parâmetros trotterStepSize que modificam a duração da simulação em cada exponencial, e trotterOrder para a ordem do integrador pretendido.As an example, the Trotter-Suzuki decomposition may be called using the following canon functions, with parameters trotterStepSize modifying the duration of simulation in each exponential, and trotterOrder for the order of the desired integrator.

function TrotterSimulationAlgorithm(
    trotterStepSize : Double, 
    trotterOrder : Int) 
: SimulationAlgorithm {
    ...
}

function TimeDependentTrotterSimulationAlgorithm(
    trotterStepSize : Double, 
    trotterOrder : Int) 
: TimeDependentSimulationAlgorithm {
    ...
}

Dica

As aplicações da biblioteca de simulação estão cobertas nas amostras.Applications of the simulation library are covered in the samples. Para uma estimativa de fase no modelo Ising SimulationAlgorithm utilizando, consulte a amostra IsingPhaseEstimation.For phase estimation in the Ising model using SimulationAlgorithm, please see the IsingPhaseEstimation sample. Para preparar o estado adiabático no modelo Ising TimeDependentSimulationAlgorithm utilizando, consulte a amostra de AdiabaticIsing.For adiabatic state preparation in the Ising model using TimeDependentSimulationAlgorithm, please see the AdiabaticIsing sample.

Preparação do Estado Adiabático & estimativa da faseAdiabatic State Preparation & Phase Estimation

Uma aplicação comum da simulação hamiltoniana é a preparação do estado adiabático.One common application of Hamiltonian simulation is adiabatic state preparation. Aqui, um é fornecido com dois Hamiltonians $H _ {\text{start}} e $H _ {\text{end}},,$H. _Here, one is provided with two Hamiltonians $H_{\text{start}}$ and $H_{\text{end}}$, and a quantum state $\ket{\psi(0)}$ that is a ground state of the start Hamiltonian $H_{\text{start}}$. Tipicamente, $H _ {\text{start}} é escolhido de tal forma que $\ket{\psi(0)}$ é fácil de preparar a partir de um estado de base computacional $\ket{0\cdots 0}$.Typically, $H_{\text{start}}$ is chosen such that $\ket{\psi(0)}$ is easy to prepare from a computational basis state $\ket{0\cdots 0}$. Ao interpolar entre estes Hamiltonianos no problema de simulação dependente do tempo suficientemente lentamente, é possível acabar, com elevada probabilidade, num estado terrestre do $H hamiltoniano final _ {\text{end}}...By interpolating between these Hamiltonians in the time-dependent simulation problem sufficiently slowly, it is possible to end up, with high probability, in a ground state of the final Hamiltonian $H_{\text{end}}$. Embora a preparação de boas aproximações aos estados terrestres de Hamiltonian possa prosseguir desta forma, invocando algoritmos de simulação hamiltoniano dependentes do tempo como uma subbroutina, outras abordagens conceptualmente diferentes, como o eigensolver quântico variacional, são possíveis.Though preparing good approximations to Hamiltonian ground states could proceed in this manner by calling upon on time-dependent Hamiltonian simulation algorithms as a subroutine, other conceptually different approaches such as the variational quantum eigensolver are possible.

Outra aplicação ubíqua na química quântica está estimando a energia do estado terrestre dos hamiltonianos que representam os passos intermédios da reação química.Yet another application ubiquitous in quantum chemistry is estimating the ground state energy of Hamiltonians representing the intermediate steps of chemical reaction. Tal esquema poderia, por exemplo, contar com a preparação do estado adiabático para criar o estado terrestre e, em seguida, incorporar uma simulação hamiltoniana independente do tempo como uma sub-rotina na caracterização da estimativa de fase para extrair esta energia com algum erro finito e probabilidade de sucesso.Such a scheme could, for instance, rely on adiabatic state preparation to create the ground state, and then incorporate time-independent Hamiltonian simulation as a subroutine in phase estimation characterization to extract this energy with some finite error and probability of success.

Abstrair algoritmos de simulação como os tipos definidos pelo utilizador SimulationAlgorithm e TimeDependentSimulationAlgorithm permitir-nos incorporar convenientemente a sua funcionalidade em algoritmos quânticos mais sofisticados.Abstracting simulation algorithms as the user-defined types SimulationAlgorithm and TimeDependentSimulationAlgorithm allow us to conveniently incorporate their functionality into more sophisticated quantum algorithms. Isto motiva-nos a fazer o mesmo por estas sub-rotinas comumente utilizadas.This motivates us to do the same for these commonly used subroutines.

Assim, definimos a função convenienteThus we define the convenient function

function InterpolatedEvolution(
        interpolationTime : Double, 
        evolutionGeneratorStart : EvolutionGenerator,
        evolutionGeneratorEnd : EvolutionGenerator,
        timeDependentSimulationAlgorithm : TimeDependentSimulationAlgorithm)
: (Qubit[] => Unit is Adj + Ctl) {
        ...
}
 

Isto devolve uma operação unitária que implementa todas as etapas da preparação do estado adiabático.This returns a unitary operation that implements all steps of adiabatic state preparation. O primeiro parâmetro interpolatedTime define o tempo sobre o qual interpolamos linearmente entre o início hamiltoniano descrito pelo segundo parâmetro e o final evolutionGeneratorStart Hamiltonian descrito pelo terceiro parâmetro evolutionGeneratorEnd .The first parameter interpolatedTime defines the time over which we linearly interpolate between the start Hamiltonian described by the second parameter evolutionGeneratorStart and the end Hamiltonian described by the third parameter evolutionGeneratorEnd. O quarto parâmetro timeDependentSimulationAlgorithm é onde se faz a escolha do algoritmo de simulação.The fourth parameter timeDependentSimulationAlgorithm is where one makes the choice of simulation algorithm. Note que se interpolatedTime for tempo suficiente, um estado inicial permanece um estado terrestre instantâneo do Hamiltonian durante toda a duração da simulação dependente do tempo, e assim termina no estado térreo do hamiltoniano final.Note that if interpolatedTime is long enough, an initial ground state remains an instantaneous ground state of the Hamiltonian over the entire duration of time-dependent simulation, and thus ends in the ground state of the end Hamiltonian.

Também definimos uma operação útil que executa automaticamente todos os passos de uma experiência típica de química quântica.We also define a helpful operation that automatically performs all steps of a typical quantum chemistry experiment. Por exemplo, temos o seguinte, que devolve uma estimativa energética do estado produzido pela preparação do estado adiabático:For instance we have the following, which returns an energy estimate of the state produced by adiabatic state preparation:

operation EstimateAdiabaticStateEnergy(
    nQubits : Int,
    statePrepUnitary : (Qubit[] => Unit),
    adiabaticUnitary : (Qubit[] => Unit),
    qpeUnitary: (Qubit[] => Unit is Adj + Ctl),
    phaseEstAlgorithm : ((DiscreteOracle, Qubit[]) => Double))
: Double {
...
}

nQubits é o número de qubits usados para codificar o estado quântico inicial.nQubits is the number of qubits used to encode the initial quantum state. statePrepUnitary prepara o estado de partida a partir da base computacional $\ket{0\cdots 0}$.statePrepUnitary prepares the start state from the computational basis $\ket{0\cdots 0}$. adiabaticUnitary é a operação unitária que implementa a preparação do estado adiabático, tal como produzido pela InterpolatedEvolution função.adiabaticUnitary is the unitary operation that implements adiabatic state preparation, such as produced by the InterpolatedEvolution function. qpeUnitary é a operação unitária que é usada para realizar a estimativa de fase no estado quântico resultante.qpeUnitary is the unitary operation that is used to perform phase estimation on the resulting quantum state. phaseEstAlgorithm é a nossa escolha de algoritmo de estimativa de fase.phaseEstAlgorithm is our choice of phase estimation algorithm.

Dica

As aplicações de preparação do estado adiabático são abrangidas pelas amostras.Applications of adiabatic state preparation are covered in the samples. Para o modelo Ising utilizando uma implementação manual da preparação do estado adiabático versus utilização da AdiabaticEvolution função, consulte a amostra de AdiabaticIsing.For the Ising model using a manual implementation of adiabatic state preparation versus using the AdiabaticEvolution function, please see the AdiabaticIsing sample. Para a estimativa de fase e preparação do estado adiabático no modelo Ising, consulte a amostra isingPhaseEstimation.For phase estimation and adiabatic state preparation in the Ising model, please see the IsingPhaseEstimation sample.

Dica

A simulação do hidrogénio molecular é uma amostra interessante e breve.The simulation of molecular Hydrogen is an interesting and brief sample. O modelo e os resultados experimentais reportados em O'Malley et al.The model and experimental results reported in O'Malley et. al. apenas requer matrizes Pauli e toma o formulário $\hat H = g _ {0} I _ 0I _ 1+g _ 1{Z _ 0}+g _ 2{Z _ 1}+g _ 3{Z _ 0}z _ 1}+g _ 4{Y _ 0}{Y _ 1}+g _ 5{X _ 0}{X _ 1}..only requires Pauli matrices and takes the form $\hat H = g_{0}I_0I_1+g_1{Z_0}+g_2{Z_1}+g_3{Z_0}{Z_1}+g_4{Y_0}{Y_1}+g_5{X_0}{X_1}$. Este é um Hamiltonian eficaz que requer apenas 2 qubits, onde as constantes $g$ são calculadas à distância $R$ entre os dois átomos de Hidrogénio.This is an effective Hamiltonian only requiring only 2 qubits, where the constants $g$ are computed from the distance $R$ between the two Hydrogen atoms. Utilizando funções canónicas, os Paulis são convertidos em unitários e depois evoluíram ao longo de curtos períodos de tempo usando a decomposição Trotter-Suzuki.Using canon functions, the Paulis are converted to unitaries and then evolved over short periods of time using the Trotter-Suzuki decomposition. Uma boa aproximação ao estado terrestre de $H_2$ pode ser criada sem a utilização de preparação do estado adiabático, pelo que a energia do estado do solo pode ser encontrada diretamente utilizando a estimativa de fase do cânone.A good approximation to the $H_2$ ground state can be created without using adiabatic state preparation, and so the ground state energy may be found directly by utilizing phase estimation from the canon.

Algoritmo de ShorShor's Algorithm

O algoritmo de Shor continua a ser um dos desenvolvimentos mais significativos na computação quântica porque mostrou que os computadores quânticos poderiam ser usados para resolver problemas importantes, atualmente clássicos, intrigantes.Shor's algorithm remains one of the most significant developments in quantum computing because it showed that quantum computers could be used to solve important, currently classically intractable problems. O algoritmo de Shor fornece uma forma rápida de factorar grandes números usando um computador quântico, um problema chamado factoring .Shor's algorithm provides a fast way to factor large numbers using a quantum computer, a problem called factoring . A segurança de muitos criptosistemas atuais baseia-se no pressuposto de que não existe algoritmo rápido para factoring.The security of many present-day cryptosystems is based on the assumption that no fast algorithm exists for factoring. Assim, o algoritmo de Shor teve um profundo impacto na forma como pensamos sobre a segurança num mundo pós-quântico.Thus Shor's algorithm has had a profound impact on how we think about security in a post-quantum world.

O algoritmo de Shor pode ser considerado como um algoritmo híbrido.Shor's algorithm can be thought of as a hybrid algorithm. O computador quântico é usado para executar uma tarefa computacionalmente difícil conhecida como descoberta de período.The quantum computer is used to perform a computationally hard task known as period finding. Os resultados da constatação do período são então processados clássicamente para estimar os fatores.The results from period finding are then classically processed to estimate the factors. Revemos estes dois passos abaixo.We review these two steps below.

Constatação do períodoPeriod Finding

Tendo visto como o quantum Fourier transforma e o trabalho de estimativa de fase (ver algoritmos quânticos), podemosusar estas ferramentas para resolver um problema computacional clássico chamado period finding .Having seen how the quantum Fourier transform and phase estimation work (see Quantum algorithms), we can use these tools to solve a classically hard computational problem called period finding . Na secção seguinte, veremos como aplicar o período de visão ao factoring.In the next section, we will see how to apply period finding to factoring.

Tendo em conta dois inteiros $a$ e $N$, onde $a<N$, o objetivo da descoberta do período, também chamado de descoberta de encomendas, é encontrar a encomenda $r$ de $a$ modulo $N$, onde $r$ é definido como o número inteiro menos positivo, tal que $a^r \equiv 1 \equiv 1 \text} mod }Given two integers $a$ and $N$, where $a<N$, the goal of period finding, also called order finding, is to find the order $r$ of $a$ modulo $N$, where $r$ is defined to be the least positive integer such that $a^r \equiv 1 \text{ mod } N$.

Para encontrar a encomenda usando um computador quântico, podemos usar o algoritmo de estimativa de fase aplicado ao seguinte operador unitário $U_a$: $$ U_a\ket{x} \equiv \ket{(ax)\text} mod }N} .$$ Os eigenvectors de $U_a$ são para o integer $s$ e $0 $$\ket{x_s} \equiv 1 / \sqrt{r} \soma _ {k=0}^{r-1} e^{\frac{-2\pi i sk}}} \ket{a^k\text{ mod},$$ são eigenstates of $U_a$.To find the order using a quantum computer, we can use the phase estimation algorithm applied to the following unitary operator $U_a$: $$ U_a\ket{x} \equiv \ket{(ax)\text{ mod }N} .$$ The eigenvectors of $U_a$ are for integer $s$ and $0\leq s \leq r - 1$, $$\ket{x_s} \equiv 1 / \sqrt{r} \sum_{k=0}^{r-1} e^{\frac{-2\pi i sk}{r}} \ket{a^k\text{ mod }N},$$ are eigenstates of $U_a$. Os valores eigenvalues de $U_a$ são $$ U _ a \ket{x _ s} = e^{2\pi i s / r} \ket{x _ s} .The eigenvalues of $U_a$ are $$ U_a \ket{x_s} = e^{2\pi i s / r} \ket{x_s} . $$

A estimativa de fases assim produz os eigenvalues $e^{2\pi i s / r}$ a partir do qual $r$ pode ser aprendido eficientemente usando frações contínuas de $s /r$.Phase estimation thus outputs the eigenvalues $e^{2\pi i s / r}$ from which $r$ can be learned efficiently using continued fractions from $s / r$.

O diagrama do circuito para a descoberta do período quântico é:The circuit diagram for quantum period finding is:

Diagrama de circuito para a descoberta do período quântico

Aqui, os qubits de $2n$ são inicializados para $\ket {0} $ e $n$ qubits são inicializados para $\ket {1} $.Here $2n$ qubits are initialized to $\ket{0}$ and $n$ qubits are initialized to $\ket{1}$. O leitor pode voltar a perguntar-se porque é que o registo quântico para deter os estados eigenes é inicializado para $\ket {1} $.The reader again may wonder why the quantum register to hold the eigenstates is initialized to $\ket{1}$. Como não se sabe a encomenda $r$ com antecedência, não podemos realmente preparar estados de $\ket{x_s}$ diretamente.As one does not know the order $r$ in advance, we cannot actually prepare $\ket{x_s}$ states directly. Felizmente, verifica-se que $1/\sqrt{r} \soma _ {s=0}^{r-1} \ket{x _ s} = \ket {1} $.Luckily, it turns out that $1/\sqrt{r} \sum_{s=0}^{r-1} \ket{x_s} = \ket{1}$. Não precisamos de preparar $\ket{x}$!We don't need to actually prepare $\ket{x}$! Podemos preparar um registo quântico de $n dólares qubits no estado $\ket {1} $.We can just prepare a quantum register of $n$ qubits in state $\ket{1}$.

O circuito contém o QFT e vários portões controlados.The circuit contains the QFT and several controlled gates. O portão QFT foi descrito anteriormente.The QFT gate has been described previously. O portão controlado $U_a$ mapeia $\ket{x}$ para $\ket{(ax)\text} mod} {1}The controlled-$U_a$ gate maps $\ket{x}$ to $\ket{(ax)\text{ mod } N}$ if the control qubit is $\ket{1}$, and maps $\ket{x}$ to $\ket{x}$ otherwise.

Para obter $(a^nx)\text{ mod} N$, podemos simplesmente aplicar $U_{a^n}$, onde calculamos $a^n \text} mod } N$ clássicamente para ligar ao circuito quântico.To achieve $(a^nx)\text{ mod } N$, we can simply apply controlled-$U_{a^n}$, where we calculate $a^n \text{ mod } N$ classically to plug into the quantum circuit.
Os circuitos para alcançar tal aritmética modular foram descritos na documentação aritmética quântica, especificamente exigimos um circuito de exponenciação modular para implementar as operações de $U controlada _ {a^i}$ .The circuits to achieve such modular arithmetic have been described in the quantum arithmetic documentation, specifically we require a modular exponentiation circuit to implement the controlled-$U_{a^i}$ operations.

Embora o circuito acima corresponda à Estimativa da Fase Quântica e permita explicitamente a descoberta da ordem, podemos reduzir o número de qubits necessários.While the circuit above corresponds to Quantum Phase Estimation and explicitly enables order finding, we can reduce the number of qubits required. Podemos seguir o método de descoberta de encomendas de Beauregard, conforme descrito na página 8 do arXiv:quant-ph/0205095v3,ou usar uma das rotinas de estimativa de fase disponíveis na Microsoft.Quantum.Characterization.We can either follow Beauregard's method for order finding as described on Page 8 of arXiv:quant-ph/0205095v3, or use one of the phase estimation routines available in Microsoft.Quantum.Characterization. Por exemplo, a Estimativa de Fase Robusta também usa um qubit extra.For example, Robust Phase Estimation also uses one extra qubit.

FactoringFactoring

O objetivo do factoring é determinar os dois fatores primos do inteiro $N$, onde $N$ é um número de $n$-bit.The goal of factoring is to determine the two prime factors of integer $N$, where $N$ is an $n$-bit number.
O factoring consiste nos passos descritos abaixo.Factoring consists of the steps described below. Os passos são divididos em três partes: uma rotina clássica de pré-processamento (1-4); uma rotina de computação quântica para encontrar a ordem de $a \text{ mod } N$ (5); e uma rotina clássica de pós-processamento para derivar os fatores primos da ordem (6-9).The steps are split into three parts: a classical preprocessing routine (1-4); a quantum computing routine to find the order of $a \text{ mod } N$ (5); and a classical postprocessing routine to derive the prime factors from the order (6-9).

A rotina clássica de pré-processamento consiste nos seguintes passos:The classical preprocessing routine consists of the following steps:

  1. Se $N$ estiver em patamar, devolva o fator principal $2$.If $N$ is even, return the prime factor $2$.
  2. Se $N=p^q$ por $p\geq1$, $q\geq2$, devolva o fator principal $p$.If $N=p^q$ for $p\geq1$, $q\geq2$, return the prime factor $p$. Este passo é realizado clássicamente.This step is performed classically.
  3. Escolha um número aleatório $a$ de modo que $1 < por < N-1$.Choose a random number $a$ such that $1 < a < N-1$.
  4. Se $\text{gcd}(a,N)>1$, devolva o fator principal $\text{gcd}(a,N)$.If $\text{gcd}(a,N)>1$, return the prime factor $\text{gcd}(a,N)$. Este passo é calculado usando o algoritmo de Euclid.This step is computed using Euclid's algorithm. Se nenhum fator principal foi devolvido, prosseguimos para a rotina quântica:If no prime factor has been returned, we proceed to the quantum routine:
  5. Ligue para o algoritmo de encontrar o período quântico para calcular a ordem $r$ de $a \text{{ mod } N$.Call the quantum period finding algorithm to calculate the order $r$ of $a \text{ mod } N$. Utilize $r$ na rotina clássica de pós-processamento para determinar os fatores primos:Use $r$ in the classical postprocessing routine to determine the prime factors:
  6. Se $r$ for estranho, volte ao passo de pré-processamento (3).If $r$ is odd, go back to preprocessing step (3).
  7. Se $r$ estiver em patamar e $a^{r/2} = -1\text{ mod }N$, volte ao passo de pré-processamento (3).If $r$ is even and $a^{r/2} = -1\text{ mod }N$, go back to preprocessing step (3).
  8. Se $\text{gcd}(a^{r/2}+1, N)$ é um fator não trivial de $N$, devolva $\text{gcd}(a^{r/2}+1, N)$.If $\text{gcd}(a^{r/2}+1, N)$ is a non-trivial factor of $N$, return $\text{gcd}(a^{r/2}+1, N)$.
  9. Se $\text{gcd}(a^{r/2}-1, N)$ é um fator não trivial de $N$, devolva $\text{gcd}(a^{r/2}-1, N)$.If $\text{gcd}(a^{r/2}-1, N)$ is a non-trivial factor of $N$, return $\text{gcd}(a^{r/2}-1, N)$.

O algoritmo de factoring é probabilístico: pode-se demonstrar que com probabilidade pelo menos metade do que $r$ será uniforme e $a^{r/2} \neq -1 \text{ mod}N$, produzindo assim um fator principal.The factoring algorithm is probabilistic: it can been shown that with probability at least one half that $r$ will be even and $a^{r/2} \neq -1 \text{ mod }N$, thus producing a prime factor. (Consulte o papel original de Shor para mais detalhes, ou um dos textos básicos de computação quântica em para obter mais informações).(See Shor's original paper for details, or one of the Basic quantum computing texts in For more information). Se um fator principal não for devolvido, então simplesmente repetimos o algoritmo do passo (1).If a prime factor is not returned, then we simply repeat the algorithm from step (1). Depois de $n tentativas de dólar, a probabilidade de todas as tentativas falharem é, no máximo, $2^{-n}$.After $n$ tries, the probability that every attempt has failed is at most $2^{-n}$. Assim, depois de repetir o algoritmo, um pequeno número de vezes o sucesso é virtualmente assegurado.Thus after repeating the algorithm a small number of times success is virtually assured.