<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Filipe Chagas Ferraz on Medium]]></title>
        <description><![CDATA[Stories by Filipe Chagas Ferraz on Medium]]></description>
        <link>https://medium.com/@filipe.chagas?source=rss-afd6aeaaa729------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*IoFcIU-IZLmhpVxfi7QBaQ.jpeg</url>
            <title>Stories by Filipe Chagas Ferraz on Medium</title>
            <link>https://medium.com/@filipe.chagas?source=rss-afd6aeaaa729------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Sun, 22 Nov 2026 09:33:58 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@filipe.chagas/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Computação Quântica na Logística]]></title>
            <link>https://medium.com/cq-em-portugu%C3%AAs/computa%C3%A7%C3%A3o-qu%C3%A2ntica-na-log%C3%ADstica-7c1bb3e4065d?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/7c1bb3e4065d</guid>
            <category><![CDATA[programação]]></category>
            <category><![CDATA[computação-quântica]]></category>
            <category><![CDATA[otimização]]></category>
            <category><![CDATA[logistica]]></category>
            <category><![CDATA[ciência-da-computação]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Sun, 08 Jun 2025 20:46:03 GMT</pubDate>
            <atom:updated>2025-06-08T20:46:03.885Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/780/1*a3ay1_IcRhIWTMiUSoDghQ.png" /><figcaption>Ilustração de um problema de localização de instalações. Fonte: <a href="https://optimization.cbe.cornell.edu/index.php?title=Facility_location_problem">https://optimization.cbe.cornell.edu/index.php?title=Facility_location_problem</a></figcaption></figure><p>Uma das áreas em que a computação quântica aplicada parece ser promissora é a otimização combinatória, que abrange diversos problemas logísticos reais. Três exemplos de problemas desse tipo são:</p><ul><li><strong>Problema do Roteamento de Veículos:</strong> dado um conjunto de <em>N</em> pontos geográficos e <em>M</em> veículos, quais são as <em>M</em> rotas mais eficientes (com menor tempo e consumo de energia) que, juntas, passam por todos os <em>N</em> pontos?</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/741/1*SSwn5C0eLoMopGxhzHKDNA.png" /><figcaption>Ilustração do problema de roteamento de veículos. DOI: 10.1109/ICoAC.2017.8441175</figcaption></figure><ul><li><strong>Problema da Localização de Instalações:</strong> como posicionar um conjunto de <em>N</em> centros logísticos em uma região (bairro, cidade, estado, etc.) de modo que minimize custos como transporte e aluguel?</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/573/1*xUrtuIXrFOAohsM6kTgTzQ.png" /><figcaption>Ilustração do problema de localização de instalações. DOI: 10.1057/s41274–016–0155–6</figcaption></figure><ul><li><strong>Problema do Empacotamento:</strong> dado um conjunto de <em>N</em> objetos para transportar, cada um com um volume e um peso, e um conjunto de até <em>M</em> contêineres, cada um com uma capacidade de volume e carga, como distribuir os <em>N</em> objetos nos contêineres de modo que minimize a quantidade de contêineres usados?</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/660/1*61CEPo3BO11bcGgNm3tFcw.png" /><figcaption>Ilustração do problema do empacotamento. DOI: 10.1155/2017/9781307</figcaption></figure><p>Esses três problemas de otimização fazem parte da classe computacional <strong>NP-hard</strong>. Problemas dessa classe não possuem algoritmos conhecidos que os resolvam de forma exata em tempo tratável e determinístico. Então, para resolvê-los, recorremos a dois grupos de algoritmos que encontram soluções “ok”, mas não necessariamente perfeitas (ótimas globais): os <strong>algoritmos gulosos</strong> e as <strong>meta-heurísticas</strong>.</p><ul><li><strong>Algoritmos gulosos</strong> são aqueles que usam algum “macete” para encontrar uma solução fácil de forma rápida em um tempo fixo (que depende da quantidade de variáveis do problema), sem ficar analisando várias possíveis soluções. Exemplo: para encontrar uma boa rota de viagem <em>[r₁, r₂, …, rₙ]</em> (onde cada <em>rᵢ</em> é um ponto de parada) passando por um conjunto de <em>N</em> pontos geográficos <em>P={p₁, p₂, …, pₙ}</em>, uma estratégia gulosa que pode ser usada é escolher o ponto de partida <em>r₁∈P</em>, escolher o ponto <em>pᵢ</em> mais próximo de <em>r₁</em> como <em>r₂</em>, e repetir o segundo passo para todas próximas paradas da rota até <em>rₙ</em>. A solução é boa, fácil de computar, mas só é a melhor possível em casos bem específicos.</li><li><strong>Algoritmos meta-heurísticos</strong> já são mais complexos e dispendiosos. Eles buscam uma solução, muitas vezes testando várias possíveis, usando algum processo lógico que sirva de “guia” para as melhores soluções do problema. O tempo de execução desses algoritmos costuma ser ajustável, e a qualidade da solução encontrada não é determinística — depende de sorte e do tempo que você deixa o algoritmo rodando.</li></ul><p>Para resolver um problema de otimização logística usando uma meta-heurística, é necessário fazer uma modelagem com os seguintes elementos:</p><ul><li>uma sequência de <strong>variáveis binárias </strong><em>s=[s₁, s₂, …, sₙ]∈𝔹ⁿ</em> que, juntas, representem uma configuração ou solução do problema;</li><li>uma <strong>função de custo</strong> <em>c=f(s)</em> que calcula o custo logístico <em>c∈ℝ</em> da solução <em>s∈𝔹ⁿ</em>;</li><li>se necessário, uma ou mais <strong>restrições</strong>. Cada restrição é uma proposição <em>g(s)∈{V,F}</em> que <em>s</em> deve satisfazer para ser considerado uma solução viável.</li></ul><p>Resolver um problema de otimização significa encontrar uma solução <em>s=[s₁, s₂, …, sₙ]</em> que minimize o custo logístico <em>c.</em></p><p>Na literatura científica da computação quântica, há diversas meta-heurísticas propostas que podem ser aplicados a problemas logísticos como os três citados acima. Neste artigo, abordo quatro: <strong>GAS</strong>, <strong>QA</strong>, <strong>QAOA </strong>e <strong>BF-DCQO</strong>.</p><h3>Grover Adaptive Search (GAS)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/520/0*Tm-jJJasfppXsla6" /><figcaption>Pseudo-código do algoritmo GAS, retirado do artigo de Gilliam, Woerner e Gonciulea.</figcaption></figure><p>GAS é uma meta-heurística de otimização baseada no algoritmo quântico de busca de Grover.</p><p>A busca de Grover é um método probabilístico que visa encontrar as sequências de valores (<em>s₁, s₂, …, sₙ</em>) que satisfazem uma proposição <em>p(s₁, s₂, …, sₙ)∈{V, F}.</em> O método GAS usa a busca de Grover como uma subrotina, executando-a várias vezes para ir encontrando soluções cada vez melhores para o problema de otimização, da seguinte maneira:</p><ol><li>Usando um método aleatório ou guloso, o custo logístico <em>c⁽¹⁾</em> de uma solução ótima local <em>s⁽¹⁾</em> é calculado.</li><li>A busca de Grover é executada para encontrar uma solução <em>s⁽²⁾</em> cujo custo logístico <em>c⁽²⁾</em> seja menor que o custo <em>c⁽¹⁾</em> encontrado anteriormente<em>.</em></li><li>O procedimento do passo 2 é repetido várias vezes, sempre com o intuito de encontrar uma nova solução <em>s⁽ⁱ⁺¹⁾</em> com custo <em>c⁽ⁱ⁺¹⁾</em> menor que <em>c⁽ⁱ⁾</em>.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/493/0*QAiNA0YmhYdEVdXK" /><figcaption>Gráficos retirado do artigo de Gilliam, Woerner e Gonciulea, demonstrando a evolução das probabilidades de obtenção das soluções de um problema de otimização com GAS.</figcaption></figure><p><strong>Pontos fortes do GAS:</strong></p><ul><li>Ele é relativamente simples, fácil de entender e de implementar. Os outros três métodos de otimização quântica que abordo neste artigo são bem mais complicados.</li></ul><p><strong>Pontos fracos do GAS:</strong></p><ul><li>GAS é um método que usa muitos <em>qubits</em>. Nele, os custos logísticos são computados como um conjunto finito e quantizado de números inteiros ou decimais. Quanto maior é a precisão necessária para calcular os custos, mais <em>qubits</em> são utilizados.</li><li>No GAS, conforme o processo de otimização avança, o tempo de processamento quântico necessário para cada rodada da busca de Grover vai aumentando. Dispositivos quânticos atuais possuem tempo de coerência limitado, o que impossibilita rodadas longas de busca.</li></ul><p><strong>Bibliografia:</strong></p><ul><li><em>Grover Adaptive Search for Constrained Polynomial Binary Optimization</em>, de Austin Gilliam, Stefan Woerner, e Constantin Gonciulea. DOI: https://doi.org/10.22331/q-2021-04-08-428</li><li><em>A Fast Quantum Mechanical Algorithm for Database Search</em>, de Lov Grover. DOI: <a href="https://doi.org/10.48550/arXiv.quant-ph/9605043">https://doi.org/10.48550/arXiv.quant-ph/9605043</a></li></ul><h3>Quantum Annealing (QA)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*T7s5Pn6Mew1MdoIP" /><figcaption>Imagem conceitual do funcionamento de um quantum annealer. DOI: 10.5194/npg-31–237–2024</figcaption></figure><p>QA é uma técnica de otimização quântica proposta inicialmente por Kadowaki e Nishimori em 1998, baseada no <strong>teorema adiabático quântico</strong>.</p><p>QA requer <em>hardware</em> quântico analógico de propósito específico. Não é possível executar essa técnica em computadores quânticos digitais (de propósito geral) como os da IBM. Uma empresa que é notável no desenvolvimento de <em>hardware</em> para QA é a <strong>D-Wave</strong>.</p><p>A nível de <em>hardware</em>, um <em>Quantum Annealer</em> como os da D-Wave é um dispositivo eletrônico que usa <em>qubits </em>supercondutores interconectados e controlados por fluxos magnéticos extremamente precisos. Esses <em>qubits </em>formam um sistema físico que modela o problema de otimização.</p><p>Ao longo de uma tarefa de otimização, os fluxos magnéticos são alterados de forma gradual e lenta, fazendo com que o sistema evolua <strong>adiabaticamente </strong>para um estado solução. Ao fim do processo, os <em>qubits</em> são medidos, colapsando em uma sequência clássica de bits que representa uma solução (ou uma boa aproximação) do problema de otimização.</p><p><strong>Pontos fortes do QA:</strong></p><ul><li>QA é altamente escalável em número de <em>qubits</em>. Atualmente, já existem <em>quantum annealers</em> de milhares de <em>qubits</em>, enquanto os computadores quânticos digitais ainda operam com poucas centenas de <em>qubits</em>.</li><li><em>Quantum annealers</em> são mais tolerantes a ruído do que computadores quânticos digitais.</li></ul><p><strong>Pontos fracos do QA:</strong></p><ul><li>Faltam opções de serviços de QA no mercado.</li><li>No processo de programação de um <em>quantum annealer</em>, normalmente se usa uma etapa de <em>embedding.</em> Nesta etapa, a quantidade de <em>qubits</em> necessários para resolver o problema pode aumentar significativamente.</li><li>Se o tempo de <em>annealing</em> não for lento o suficiente, o sistema tende a evoluir de forma não adiabática, o que prejudica a qualidade dos resultados.</li></ul><p><strong>Bibliografia:</strong></p><ul><li><em>Quantum Annealing in The Transverse Ising Model</em>, de Tadashi Kadowaki e Hidetoshi Nishimori. DOI: <a href="https://doi.org/10.1103/PhysRevE.58.5355">https://doi.org/10.1103/PhysRevE.58.5355</a></li><li><em>What is Quantum Annealing?</em>, de D-Wave. URL: <a href="https://docs.dwavequantum.com/en/latest/quantum_research/quantum_annealing_intro.html#qpu-quantum-annealing-intro">https://docs.dwavequantum.com/en/latest/quantum_research/quantum_annealing_intro.html#qpu-quantum-annealing-intro</a></li><li><em>Annealing Implementation and Controls</em>, de D-Wave. URL: <a href="https://docs.dwavequantum.com/en/latest/quantum_research/annealing.html#qpu-annealing">https://docs.dwavequantum.com/en/latest/quantum_research/annealing.html#qpu-annealing</a></li></ul><h3>Quantum Approximate Optimization Algorithm (QAOA)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/470/0*fn0wxKaba26cfMeL" /><figcaption>Diagrama simplificado do algoritmo QAOA. Fonte: Matlab Help Center</figcaption></figure><p>QAOA é um algoritmo de otimização híbrido (quântico e clássico) do grupo dos <strong>algoritmos quânticos variacionais (VQAs)</strong>.</p><p>VQAs são algoritmos em que um computador quântico digital é usado para executar uma subrotina quântica parametrizada. A subrotina é executada múltiplas vezes, e um otimizador clássico faz ajustes nos parâmetros dela a cada iteração.</p><p>A subrotina quântica do QAOA possui 3 etapas:</p><ol><li>preparação de um estado quântico inicial de superposição;</li><li>adição de <em>N</em> camadas de instruções quânticas parametrizadas, onde cada camada é composta por um <strong>operador de custo</strong> e um de <strong>mistura</strong>;</li><li>medição do estado quântico, que resulta em uma sequencia clássica de bits da qual uma solução <em>s⁽ⁱ⁾ </em>é obtida.</li></ol><p>O <strong>operador de custo</strong> serve, a grosso modo, para calcular o custo logístico de cada possível solução do problema de otimização. Em cada camada, este operador possui um parâmetro <em>γᵢ</em>.</p><p>Já o<strong> operador de mistura</strong> serve para induzir mudanças no estado quântico dos <em>qubits</em>, levando-os gradualmente para o estado solução. Em cada camada, um parâmetro <em>βᵢ</em> é associado ao respectivo operador de mistura.</p><p>Os parâmetros <em>[γ₁,…,γₙ,β₁,…,βₙ]</em> são ajustados iterativamente por um algoritmo clássico de otimização numérica com o objetivo de reduzir o custo <em>c⁽ⁱ⁾</em> de cada solução <em>s⁽ⁱ⁾</em>. Para fazer esses ajustes, métodos de gradiente semelhantes aos que são usados para treinar redes neurais podem ser usados.</p><p><strong>Pontos fortes do QAOA:</strong></p><ul><li>QAOA é pensado para se ajustar bem aos computadores quânticos digitais limitados que temos atualmente. O tempo de processamento quântico das etapas 1–3 é ajustável, constante ao longo das iterações, e não necessariamente longo.</li><li>Não requer <em>hardware</em> quântico de propósito específico.</li><li>No QAOA, a precisão dos custos logísticos não depende do número de <em>qubits</em>, pois são computados como autovalores do operador de custo.</li></ul><p><strong>Pontos fracos do QAOA:</strong></p><ul><li>Um obstáculo típico de algoritmos quânticos variacionais são os <em>Barren Plateaus</em> (BPs). Em termos simples, BPs são “armadilhas” em que o computador clássico pode cair durante o processo de ajuste dos parâmetros <em>[γ₁,…,γₙ,β₁,…,βₙ]</em>, travando a otimização.</li><li>O ruído dos computadores quânticos atuais também atrapalha no ajuste dos parâmetros.</li><li>O custo logístico é computado por aproximação pelo operador de custo. Quanto mais precisa é essa aproximação, maior é o tempo de processamento quântico necessário.</li></ul><p><strong>Bibliografia:</strong></p><ul><li><em>A Quantum Approximate Optimization Algorithm</em>, de Edward Farhi, Jeffrey Goldstone e Sam Gutmann. DOI: <a href="https://doi.org/10.48550/arXiv.1411.4028">https://doi.org/10.48550/arXiv.1411.4028</a></li><li><em>A Review on Quantum Approximate Optimization Algorithm and its Variants</em>, de Kostas Blekos, Dean Brand, Andrea Ceschini, Chiao-Hui Chou, Rui-Hao Li, Komal Pandya e Alessandro Summer. DOI: <a href="https://doi.org/10.1016/j.physrep.2024.03.002">https://doi.org/10.1016/j.physrep.2024.03.002</a></li></ul><h3>Bias Field Digitalized Counterdiabatic Quantum Optimization (BF-DCQO)</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/599/0*9cuJJWUI0x_Ww6N1" /><figcaption>Ilustração do BF-DCQO retirada do paper original de Cadavid et al.</figcaption></figure><p>BF-DCQO é uma meta-heurística inspirada no teorema adiabático quântico — o mesmo que fundamenta a técnica de QA. O algoritmo foi publicado em abril deste ano (2025) por Alejandro Cadavid, Archismita Dalal, Anton Simen, Enrique Solano e Narendra N. Hegade.</p><p>BF-DCQO é um método de otimização quântica adiabática (AQO) aproximada e digitalizada que pode ser executado em computadores quânticos de propósito geral.</p><p>Uma característica importante do algoritmo BF-DCQO é que ele adiciona um termo contradiabático ao sistema, que suprime transições não adiabáticas indesejadas no estado dos <em>qubits</em>. Como explicado na seção sobre QA, transições não adiabáticas prejudicam a qualidade das soluções.</p><p>Tal como o QAOA, BF-DCQO fragmenta o processamento quântico em “rodadas” de uma subrotina quântica de duração fixa e curta, enquanto o processamento entre as rodadas é feito por um computador clássico. No entanto, em contraste com o QAOA, BF-DCQO não é um algoritmo variacional (ou seja, não envolve otimização clássica de parâmetros). O trabalho do computador clássico é muito mais leve no BF-DCQO do que no QAOA.</p><p><strong>Pontos fortes do BF-DCQO:</strong></p><ul><li>Não requer <em>hardware </em>quântico de propósito específico.</li><li>As rodadas de processamento quântico são rápidas, o que reduz o ruído.</li><li>Por não ser variacional, seu processamento clássico é leve e não sofre com <em>Barren Plateaus</em>.</li><li>Assim como no QAOA, a precisão dos custos logísticos no BF-DCQO não depende do número de <em>qubits</em>.</li></ul><p>Por se tratar de uma técnica nova que comecei a estudar recentemente, não tenho uma lista de pontos fracos para pontuar com segurança.</p><p><strong>Bibliografia:</strong></p><ul><li><em>Bias-field Digitized Counterdiabatic Quantum Optimization</em>, de Alejandro Cadavid, Archismita Dalal, Anton Simen, Enrique Solano e Narendra N. Hegade. DOI: <a href="https://doi.org/10.1103/PhysRevResearch.7.L022010">https://doi.org/10.1103/PhysRevResearch.7.L022010</a></li></ul><h3>Considerações finais</h3><p>Este artigo não tem como objetivo realizar um <em>benchmarking </em>entre métodos de otimização aplicados à logística, nem afirmar que as abordagens quânticas descritas superam os métodos clássicos existentes. O desempenho de qualquer meta-heurística depende de diversos fatores, como a convexidade do problema, o número de variáveis envolvidas, o grau polinomial da função de custo e a natureza das restrições. No caso das meta-heurísticas quânticas, há ainda uma forte dependência de características específicas do <em>hardware</em>, como tempo de coerência, número de <em>qubits </em>disponíveis e a conectividade entre eles.</p><p><strong>Este artigo também está no LinkedIn: </strong><a href="https://www.linkedin.com/pulse/computa%C3%A7%C3%A3o-qu%C3%A2ntica-na-log%C3%ADstica-filipe-chagas-ferraz-lrt4f">https://www.linkedin.com/pulse/computa%C3%A7%C3%A3o-qu%C3%A2ntica-na-log%C3%ADstica-filipe-chagas-ferraz-lrt4f</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=7c1bb3e4065d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/cq-em-portugu%C3%AAs/computa%C3%A7%C3%A3o-qu%C3%A2ntica-na-log%C3%ADstica-7c1bb3e4065d">Computação Quântica na Logística</a> was originally published in <a href="https://medium.com/cq-em-portugu%C3%AAs">CQ em Português</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[DLQ — um projeto de linguagem de programação para computação quântica]]></title>
            <link>https://medium.com/cq-em-portugu%C3%AAs/dlq-um-projeto-de-linguagem-de-programa%C3%A7%C3%A3o-para-computa%C3%A7%C3%A3o-qu%C3%A2ntica-f11e96bd13ff?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/f11e96bd13ff</guid>
            <category><![CDATA[linguagem-de-programação]]></category>
            <category><![CDATA[programação-declarativa]]></category>
            <category><![CDATA[dlq]]></category>
            <category><![CDATA[computação-quântica]]></category>
            <category><![CDATA[compiladores]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Fri, 16 Jun 2023 06:01:09 GMT</pubDate>
            <atom:updated>2026-09-02T22:16:43.881Z</atom:updated>
            <content:encoded><![CDATA[<h3>Declarative Language for Quantum (DLQ)— um projeto de linguagem de programação para computação quântica</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wvqCzMuc4dGYxLqjdG7G0g.png" /><figcaption>Ideia de logo para a DLQ, feita com ajuda do <a href="https://www.autodraw.com/">autodraw.com</a>, referenciando o famoso Gato de Schrödinger — um experimento mental criado pelo físico <a href="https://pt.wikipedia.org/wiki/Erwin_Schr%C3%B6dinger">Erwin Schrödinger</a> para ilustrar a interpretação de Copenhague da mecânica quântica. Aceito sugestões de outras ideias de logo!</figcaption></figure><p>DLQ (<em>Declarative Language for Quantum</em>) é uma pequena linguagem de programação que fiz como Trabalho de Conclusão de Curso (TCC) de Engenharia de Computação. Como o próprio nome sugere, é uma linguagem declarativa e direcionada à programação de computadores quânticos. Atualmente, ela pode ser usada para resolver, especificamente, problemas de satisfatibilidade de expressões algébricas simples, compostas por números naturais e operadores lógicos, aritméticos e relacionais. O escopo da versão inicial da linguagem, que apresentei para a banca avaliadora na defesa do meu TCC, se concentra neste tipo de aplicação e em poucas <em>features</em>. No entanto, futuramente, com a adição de novos recursos, outras aplicações podem ser consideradas, como otimização combinatória e contagem de soluções.</p><p>Minha motivação para escrever este artigo informal é que, por ser um projeto <em>open-source</em> que me deu muito trabalho para desenvolver (e, diga-se de passagem, eu poderia ter um TCC aprovado com muito menos trabalho), não quero simplesmente deixá-lo às moscas em um repositório abandonado do Github. Por isso, venho por meio deste <em>post</em> divulgar o projeto.</p><p>Ao longo deste artigo, irei dar uma visão geral sobre computação quântica, aspectos gerais da linguagem (ideias e características), características do compilador, e também perspectivas: melhorias que devem ser feitas, problemas técnicos que devem ser corrigidos e ideias para o futuro. Para aqueles que quiserem conhecer o projeto mais a fundo, sugiro a leitura da monografia (cujo <em>link</em> está disponível na seção de sugestões de leitura) e do código-fonte do compilador (<em>link</em> para o repositório no final da seção “O compilador <em>DLQpiler</em>”).</p><h3>Visão geral de computação quântica</h3><p>Esta seção é dedicada àqueles que nunca ouviram falar — ou só não pesquisaram a fundo — sobre computação quântica. E desde já, esclareço que sei que há uma moda em produtos, serviços e conteúdos que usam os termos “quântico” e “física quântica” de forma indevida, desrespeitosa e fraudulenta. Não compactuo com essa moda. Tudo que escrevo aqui referente à computação quântica é embasado em referências científicas confiáveis, como artigos e livros acadêmicos. Inclusive, ao fim deste artigo, faço algumas recomendações de livros e artigos para ler.</p><p>Computação quântica é um paradigma de computação em recente ascensão (porém não novo) que tem como base a teoria da computação, a mecânica quântica e a teoria da informação quântica. Alguns dos principais nomes do pioneirismo nesta área são Feynman [10], Deutsch [9], Shor [11] e Grover [1]. A ideia deste paradigma é usar as propriedades “especiais” dos sistemas quânticos para resolver problemas computacionais com alguma redução em tempo de computação. Duas dessas propriedades especiais são: a superposição quântica, que é a capacidade que sistemas quânticos têm de existir em somas de estados que classicamente seriam mutuamente exclusivos, e o emaranhamento quântico, explicado mais adiante. Para fazer computações utilizando essas propriedades de sistemas quânticos, utilizam-se os <strong>computadores quânticos.</strong></p><p>O princípio básico da computação quântica é o uso de <em>bits</em> quânticos, ou simplesmente <em>qubits</em>. O <em>qubit</em> é uma unidade de informação que, assim como o <em>bit</em> clássico, tem dois níveis lógicos, que são usualmente representados como 0 e 1. Em contraste com o <em>bit</em> clássico, que só pode existir em um nível lógico por vês, o <em>qubit</em> pode ter dois níveis lógicos ao mesmo tempo, pelo fenômeno da superposição quântica.</p><p>Os níveis lógicos do <em>qubit</em> são descritos algebricamente como vetores ortogonais unitários <strong>|0⟩ = [1 0]ᵀ</strong> e <strong>|1⟩ = [0 1]ᵀ</strong>, onde <strong>|0⟩ </strong>e <strong>|1⟩ </strong>são análogos dos respectivos níveis lógicos clássicos <strong>0</strong> e <strong>1</strong>.</p><p>O estado de um <em>qubit </em>é descrito como uma combinação linear de <strong>|0⟩ </strong>e <strong>|1⟩</strong>, como mostra a seguinte equação:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/530/1*S_733a7y86ti24Puwil2Fg.png" /><figcaption>(1)</figcaption></figure><p>Nesta equação, <strong>|ψ⟩ </strong>é o estado de um <em>qubit</em> e <strong>(w₀,w₁)</strong> são coeficientes complexos denominados “amplitudes de probabilidade”.</p><p>Quando o estado de um <em>qubit</em> é medido instrumentalmente (e não vou entrar em detalhes de como isso é feito fisicamente, porque meu <em>background</em> é computação, não física), ocorre o <strong>colapso do estado quântico</strong>, que faz com que um dos níveis lógicos <strong>|0⟩ </strong>e <strong>|1⟩ </strong>seja observado de forma indeterminística. As probabilidades de observação desses níveis lógicos são, respectivamente, <strong>|w₀|²</strong> e <strong>|w₁|²</strong>.</p><p>Também há estados quânticos compostos por múltiplos <em>qubits</em>. Por exemplo: os estados de 2 <em>qubits</em> <strong>|0,0⟩</strong>, <strong>|0,1⟩</strong>, <strong>|1,0⟩</strong> e <strong>|1,1⟩</strong>, que também podem ser grafados como <strong>|0⟩</strong>, <strong>|1⟩</strong>, <strong>|2⟩</strong> e <strong>|3⟩</strong>, correspondem a, respectivamente, <strong>[1 0 0 0]ᵀ</strong>, <strong>[0 1 0 0]ᵀ</strong>, <strong>[0 0 1 0]ᵀ</strong> e <strong>[0 0 0 1]ᵀ</strong>.</p><p><em>Qubits</em> podem ser conectados de forma que seus estados sejam inseparáveis e suas probabilidades de colapso sejam correlacionadas. Isto é o chamado <strong>emaranhamento quântico</strong>. Um exemplo de estado com emaranhamento é o estado Bell, definido na equação a seguir:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/226/1*DwuOj850SrrAltsaL-Ojyg.png" /><figcaption>(2)</figcaption></figure><p>Este estado é composto por 2 <em>qubits</em>. Quando esses <em>qubits</em> são submetidos a medições, os níveis lógicos observados são sempre <strong>|0⟩|0⟩ </strong>ou <strong>|1⟩|1⟩</strong>.</p><p>O processamento dos estados dos <em>qubits</em> é feito por <strong>circuitos quânticos</strong> compostos por <strong>portas lógicas quânticas</strong>. Uma “porta lógica quântica” é uma terminologia para uma matriz unitária de <strong>2ⁿ</strong> linhas e colunas que processa estados de <strong>n</strong> <em>qubits</em>. Já um <strong>circuito quântico</strong> é uma representação diagramática de algoritmo quântico que consiste em uma cadeia de portas lógicas quânticas aplicadas sobre um conjunto de <em>qubits</em>. A combinação das operações de um circuito quântico, entre a inicialização e a medição dos <em>qubits,</em> também corresponde a uma matriz unitária de <strong>2ⁿ</strong> linhas e colunas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/732/1*AZJs8o4juegmN2OF1qe99Q.png" /><figcaption>Exemplos de portas lógicas quânticas (figura extraída de Wikimedia Commons, de autoria de Rxtreme, sob licença CC BY-SA 4.0 &lt;<a href="https://creativecommons.org/licenses/by-sa/4.0">https://creativecommons.org/licenses/by-sa/4.0</a>&gt;)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*EmnI8PReCCuaE2dqG-DWVQ.png" /><figcaption>Exemplo de circuito quântico de 2 qubits, 2 portas lógicas quânticas unitárias (Hadamard e Controlled-NOT), e 2 portas não unitárias de medição</figcaption></figure><p>Cada porta lógica quântica faz uma transformação no estado dos <em>qubits</em> com alguma finalidade. A porta Pauli-X, por exemplo, pode ser pensada como um análogo quântico da porta lógica clássica <em>not</em>, pois faz as transformações <strong>|0⟩↦|1⟩</strong> e <strong>|1⟩↦|0⟩</strong>. Já as portas Controlled-NOT e Toffoli fazem, respectivamente, as transformações <strong>|x, y⟩↦|x, x⊕y⟩</strong> e <strong>|x, y, z⟩↦|x, y, z⊕xy⟩</strong>, onde <strong>(x,y,z)∈{0,1}³</strong>. A compreensão do papel de cada uma das demais portas lógicas quânticas requer um estudo mais aprofundado sobre o tema. Caso o leitor se interesse, recomendo a leitura dos artigos <a href="https://medium.com/cq-em-portugu%C3%AAs/do-bit-ao-qubit-113975dca0">Qubits</a> e <a href="https://medium.com/cq-em-portugu%C3%AAs/portas-l%C3%B3gicas-qu%C3%A2nticas-ed014c43a381">Portas Lógicas Quânticas</a>.</p><p>É evidente que circuitos quânticos são representações análogas aos circuitos digitais clássicos, compostos por portas lógicas <em>not</em>, <em>and</em>, <em>or</em>, <em>xor</em>, <em>nand</em> e <em>nor</em>. Inclusive, qualquer circuito digital combinacional clássico pode ser “traduzido” em um circuito quântico (as vezes requerendo alguns <em>qubits</em> extras), o que inclui circuitos aritméticos (que fazem operações como soma, subtração e multiplicação com <em>bits</em>) e relacionais (que fazem comparações de igualdade, não-igualdade, menor-que e maior-que). Exemplos de trabalhos que tratam de circuitos quânticos aritméticos e relacionais são os artigos de Vedral et al. [5], Draper [6], Ruiz-Perez &amp; Garcia-Escartin [7], e minha monografia.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*40ohQZyFCZhxbPt6wczKog.png" /><figcaption>Circuitos quânticos análogos as portas lógicas clássicas not, and e or, os quais chamo de “circuitos quânticos lógicos”</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/662/1*oeD8PCTQWoZ7TGQQTxbYXg.png" /><figcaption>Comparação lado-a-lado das versões clássica e quântica do somador completo de 1 bit/qubit</figcaption></figure><p>Circuitos quânticos aritméticos e relacionais têm uma vantagem sobre seus equivalentes clássicos, proveniente da própria linearidade das portas lógicas quânticas, que é a capacidade de processamento paralelo. Talvez o leitor não se lembre de ter visto isso nas aulas de álgebra linear (ou talvez nem tenha estudado álgebra linear), mas qualquer operador linear <strong>F</strong> (que pode ser uma matriz unitária) tem a seguinte propriedade:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/615/1*Tsr4k5pLgmc178L-3b6mFQ.png" /><figcaption>(3)</figcaption></figure><p>Ou seja: aplicando uma função linear sobre uma superposição de dados, obtemos uma superposição de cada um desses dados “processado” pela função. Por exemplo: um somador quântico pode ser definido como uma matriz unitária <strong>U</strong> tal que <strong>U|x⟩ = |x+c⟩</strong>. Aplicando essa matriz a um estado de superposição <strong>|X⟩ = (|0⟩+|2⟩+|4⟩+|6⟩)/√4</strong>,<strong> </strong>considerando <strong>c=1</strong>, temos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/891/1*CyU5zD1Qn_VosIp61wu4Xw.png" /><figcaption>(4)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/532/1*AwfaYOJOlH-_nHTKc90few.png" /><figcaption>Somador quântico baseado em transformada de Fourier quântica (QFT)</figcaption></figure><p>Como mostra a equação acima, tínhamos uma superposição dos valores 0, 2, 4 e 6, que processamos paralelamente usando a matriz unitária <strong>U</strong>, obtendo uma superposição dos valores 1, 3, 5 e 7. É como uma instrução SIMD de um computador clássico, só que usando fenômenos quânticos ao invés de múltiplos processadores digitais. Mas há um problema: quando os <em>qubits</em> desse sistema são submetidos a uma medição conjunta, apenas um dos valores da superposição é obtido de forma aleatória (lembre-se do que foi dito sobre <strong>colapso do estado quântico</strong> logo acima). Então, algo a mais é necessário para que esse poder de processamento paralelo se torne útil na prática, e é aí que entra o <strong>algoritmo de Grover</strong>.</p><p>O algoritmo de Grover é um algoritmo quântico de busca em conjuntos de dados não ordenados criado pelo cientista da computação Lov Grover [1]. O que esse algoritmo faz é, basicamente, “marcar” os dados da superposição que satisfazem uma determinada condição usando um operador oracular <strong>Uₒ: |x⟩↦ (−1)ᶠ⁽ˣ⁾ |x⟩</strong>, e aumentar a probabilidade de observação desses estados usando um operador de difusão <strong>Uₛ=2|s⟩⟨s|−I</strong>. Com isso, podemos usar circuitos quânticos lógicos, aritméticos e relacionais para resolver problemas de <strong>satisfatibilidade</strong>.</p><p>Um problema de satisfatibilidade pode ser enunciado, de modo geral, da seguinte forma: encontre uma tupla de valores <strong>(v₁,v₂,…,vₙ)</strong> que satisfaça <strong>f(v₁,v₂,…,vₙ)=1</strong>, onde <strong>f(⋅)</strong> é uma função binária (que resulta em 0 ou 1), e os <strong>v</strong>’s são valores numéricos. Três exemplos de problemas computacionais que podem ser definidos como problemas de satisfatibilidade são:</p><ul><li><strong>satisfatibilidade booleana</strong>, que consiste em encontrar uma tupla de valores binários que satisfaz uma determinada expressão booleana;</li><li><strong>fatoração prima</strong>, que consiste em encontrar, para um número natural <strong>k</strong>, um par de números primos <strong>(p₁,p₂)</strong> que satisfaz <strong>p₁p₂=k.</strong></li><li><strong>resolução de sistemas de equações</strong>, que consiste em encontrar a solução de um conjunto de equações que compartilham as mesmas incógnitas.</li></ul><p>Não sei se consegui fazê-lo entender esses conceitos de computação quântica. Se não consegui, não há problema, pois minha verdadeira intenção com essa seção é mostrar como é complexo programar um computador quântico “na unha”. E foi por isso que criei a linguagem DLQ: para abstrair toda essa matemática, facilitando a programação dos computadores quânticos.</p><h3>Idealização da DLQ</h3><p>A ideia básica que tive quando comecei a pensar criar em uma linguagem de programação para computação quântica foi utilizar circuitos quânticos lógicos, aritméticos e relacionais para criar uma linguagem com expressões formadas por operadores lógicos, aritméticos e relacionais. Para que isso fosse útil na prática, esses circuitos lógicos, aritméticos e relacionais seriam associados a um algoritmo de busca, otimização ou contagem, como o algoritmo de busca de Grover [1], o algoritmo quântico de contagem [8] e o algoritmo quântico de otimização aproximada (QAOA) [2].</p><p>Ao longo do tempo, até começar a de fato programar o compilador, pensei em várias formas diferentes de criar um paradigma completo que abstraísse os circuitos quânticos e os fenômenos da superposição e do emaranhamento quântico. Uma das primeiras ideias foi criar uma linguagem estruturada onde os estados quânticos fossem representados por estruturas de dados como <em>array</em>, <em>set</em> e <em>map</em>. Demorou um pouco, mas percebi que era uma ideia ruim. Em programação estruturada, frequentemente fazemos operações que não são possíveis ou são muito custosas na computação quântica, como criar cópias independentes de estruturas de dados (<a href="https://en.wikipedia.org/wiki/No-cloning_theorem"><em>no-cloning theorem</em></a>), sobrepor estados e iterar por tempo indefinido. Essas duas últimas são operações irreversíveis. Na computação quântica, todas as operações entre a inicialização e a medição dos <em>qubits</em> são reversíveis. Outra ideia foi criar uma linguagem funcional onde os estados quânticos de superposição seriam representados por variáveis aleatórias de espaço amostral e probabilidades imutáveis. Esta última ideia é melhor do que a primeira, mas ainda tem um problema: criar uma linguagem funcional do zero é complicado. Não vale a pena trabalhar com um escopo tão amplo em um TCC. Além disso, nunca havia estudado sobre cálculo lambda, que é a base do paradigma funcional. A última ideia foi criar uma linguagem declarativa que, assim como as linguagens funcionais, não admitisse sobreposição de estados, mas que não tivesse recursos “complicados” de programação funcional, como funções lambda, recursividade, estruturas de dados e operadores como <em>map</em>, <em>filter</em> e <em>reduce</em>. Esta última foi a ideia que saiu do papel.</p><p><strong>Obs.: sobreposição ≠ superposição. Não confunda!</strong></p><h3>Sintaxe e lógica da DLQ</h3><p>A estrutura de um código DLQ é composta pelos seguintes elementos:</p><ul><li><strong>variáveis</strong>, que são símbolos matemáticos definidos em termos de conjuntos numéricos ou expressões;</li><li><strong>operadores lógicos, aritméticos e relacionais</strong>, que são os símbolos que compõem as expressões;</li><li><strong>terminadores</strong>. Um terminador é a sentença final de um código. Sua função é especificar o tipo de problema a ser resolvido (busca, otimização, contagem de soluções, etc.) e os detalhes de como deve ser resolvido.</li></ul><p>Na versão da linguagem que apresentei para a banca avaliadora, os operadores lógicos, aritméticos e relacionais disponíveis são:</p><ul><li>lógica <em>not</em> (“<strong>not &lt;expressão&gt;</strong>”)</li><li>lógica <em>and</em> (“<strong>&lt;expressão&gt; and &lt;expressão&gt;</strong>”)</li><li>lógica <em>or</em> (“<strong>&lt;expressão&gt; or &lt;expressão&gt;</strong>”)</li><li>soma (“<strong>&lt;expressão&gt; + &lt;expressão&gt;</strong>”)</li><li>subtração (“<strong>&lt;expressão&gt; - &lt;expressão&gt;</strong>”)</li><li>multiplicação (“<strong>&lt;expressão&gt; * &lt;expressão&gt;</strong>”)</li><li>potenciação (“<strong>&lt;expressão&gt; ^ &lt;número&gt;</strong>”)</li><li>igualdade (“<strong>&lt;expressão&gt; = &lt;expressão&gt;</strong>”)</li><li>não-igualdade (“<strong>&lt;expressão&gt; != &lt;expressão&gt;</strong>”)</li><li>maior-que (“<strong>&lt;expressão&gt; &gt; &lt;expressão&gt;</strong>”)</li><li>menor-que (“<strong>&lt;expressão&gt; &lt; &lt;expressão&gt;</strong>”)</li></ul><p>Nesta versão, só há um terminador: o <strong><em>amplify</em></strong>. A função deste terminador é buscar as soluções de uma expressão binária usando o algoritmo de Grover. Em versões futuras da linguagem, outros terminadores podem ser adicionados.</p><p>Em um programa DLQ, todas as linhas, com exceção da última, definem variáveis. Essas não são como variáveis de linguagens imperativas (como C, C++, Java e Python), que, a grosso modo, representam pequenos espaços de memória com estado mutável. Variáveis em DLQ são imutáveis e não necessariamente possuem valor definido até que o programa termine de ser executado, mas possuem conjuntos de valores possíveis. Elas podem ser definidas como segue:</p><ul><li><strong>Definição em pertinência — </strong>forma de definir uma variável na qual se declara o conjunto de valores que esta pode assumir.</li></ul><pre>&lt;nome&gt; [&lt;tamanho&gt;] in {&lt;valor1&gt;, &lt;valor2&gt;, &lt;...&gt;, &lt;valorN&gt;};</pre><ul><li><strong>Definição em expressão </strong>— forma de definir uma variável na qual esta é descrita como o resultado de uma expressão, sendo, portanto, dependente de outras variáveis.</li></ul><pre>&lt;nome&gt; [&lt;tamanho&gt;] := &lt;expressão&gt;;</pre><p>Nos blocos de código acima, “&lt;nome&gt;” representa o nome da variável, “&lt;tamanho&gt;” representa o tamanho da variável em número de <em>qubits</em>, “&lt;expressão&gt;” representa uma expressão formada pelos operadores já citados, e “&lt;valor1&gt;, &lt;valor2&gt;, &lt;…&gt;, &lt;valorN&gt;” representa uma sequência de <strong>N</strong> números naturais.</p><p>No processo de compilação, uma variável definida como pertencente a um conjunto de números naturais <strong>{v₁, v₂, …, vₙ}</strong> se “traduz” em um <strong>registrador quântico</strong> (nome que damos a uma sequência de <em>qubits</em>) que, antes da aplicação do operador oracular e da difusão de Grover, tem um estado de superposição <strong>(|v₁⟩+|v₂⟩+…+|vₙ⟩)/√n</strong> . Já uma variável definida como resultado de uma expressão <strong>f(⋅)</strong> se “traduz” em um registrador quântico usado como registrador de “saída” da cadeia de circuitos lógicos, aritméticos e relacionais que resolvem <strong>f(⋅)</strong>.</p><p>A última linha do programa DLQ é sempre dedicada ao terminador <em>amplify</em>. Este terminador tem a seguinte sintaxe:</p><pre>amplify &lt;nome&gt; &lt;número&gt; times</pre><p>Neste bloco de código, “&lt;nome&gt;” representa o nome da variável alvo da busca, e “&lt;número&gt;” representa o número de iterações do algoritmo de Grover. A variável alvo é uma variável binária (de 1 <em>qubit</em>) usada como condicional da busca.</p><p>Para cada programa, existe um número ideal de iterações do algoritmo de Grover, calculado a partir do tamanho <strong>N</strong> do espaço de busca e da quantidade <strong>s</strong> de soluções presentes. Nos casos em que essa quantidade de soluções não é conhecida, faz-se uma suposição (um chute) do valor de <strong>s</strong>. Nas próximas seções, este cálculo de número de iterações é explicado e exemplificado.</p><h4>Exemplo 1 — satisfatibilidade booleana em DLQ</h4><p>Para deixar a explicação mais clara, segue um exemplo de código em DLQ que resolve a expressão <strong>(x₁ ∨ ¬x₃ ∨ x₄) ∧ (¬x₂ ∨ x₃ ∨ ¬x₄)</strong>.</p><pre>x1[1] in {false, true};<br>x2[1] in {false, true};<br>x3[1] in {false, true};<br>x4[1] in {false, true};<br>y[1] := (x1 or not x3 or x4) and (not x2 and x3 and not x4);<br>amplify y 3 times</pre><p>Encontrar a solução de uma expressão composta por variáveis binárias e operadores lógicos é um problema clássico da computação conhecido como <strong>problema da satisfatibilidade booleana</strong>. Este foi o primeiro problema computacional a ser provado NP-completo.</p><p>No código apresentado acima, 5 variáveis são definidas: <strong>x1</strong>, <strong>x2</strong>, <strong>x3</strong>, <strong>x4</strong> e <strong>y</strong>. Todas são variáveis de 1 <em>qubit.</em> As primeiras 4 são definidas como pertencentes ao conjunto <strong>{false, true}</strong> (que é o mesmo que <strong>{0, 1}</strong>), e a variável <strong>y</strong> é definida como o resultado da expressão booleana. Na última linha, o terminador <em>amplify</em> é aplicado para “marcar” e buscar, com 3 iterações do algoritmo de Grover, as tuplas de valores <strong>(x1, x2, x3, x4, y)</strong> nas quais <strong>y=1.</strong> De modo geral, esse número de iterações deve ser calculado como <strong>⌊(π/4)*sqrt(N/s)⌋</strong>,<strong> </strong>onde <strong>N </strong>é o tamanho do espaço de busca e <strong>s</strong> é a quantidade de soluções marcadas. Como há 4 variáveis binárias independentes no código, existem, no total, <strong>2⁴</strong> tuplas de valores <strong>(x1, x2, x3, x4, y) </strong>possíveis<strong>.</strong> Pressupondo que há apenas uma solução para a expressão booleana, o número de iterações do algoritmo de Grover é, então, calculado como <strong>⌊(π/4)*sqrt(2⁴/1)⌋=3</strong>.</p><p>A compilação deste exemplo de código, com o compilador <em>DLQpiler</em>, gera o seguinte circuito quântico:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*PyuREFUSEFlZh8EfQf5AJw.png" /><figcaption>Circuito quântico gerado pelo compilador DLQpiler a partir do exemplo de código de satisfatiblidade booleana com 4 variáveis</figcaption></figure><p>Executando este circuito quântico com o simulador <em>aer_simulador</em>, da plataforma Qiskit, obtemos a seguinte tabela de resultados:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/491/1*9SrpxYsktbfaWVLocg3dgQ.png" /><figcaption>Tabela de resultados da simulação do exemplo de satisfatibilidade booleana em DLQ, usando o simulador aer_simulator, com 1024 shots de simulação</figcaption></figure><p>Sei que, à primeira vista, pode ser difícil interpretar esta tabela. Vamos lá: circuitos quânticos sempre são executados com um determinado número de <em>shots. </em>O número de <em>shots</em> é a quantidade de vezes que todo o procedimento descrito no circuito quântico, da iniciação até a medição dos <em>qubits</em>, é “rodado”. Em cada uma dessas “rodadas” do circuito quântico, um resultado é obtido de forma indeterminística. Cada resultado possível do circuito quântico tem uma probabilidade de ser obtido em uma “rodada”. O que geralmente fazemos para analisar o comportamento de um algoritmo quântico é executá-lo com um número grande de <em>shots</em> e organizar os resultados em um histograma ou uma tabela com uma coluna de frequência absoluta.</p><p>Na tabela acima, vemos uma coluna para cada variável e, por último, uma coluna de frequência absoluta. Cada linha da tabela corresponde a uma das <strong>2⁴</strong> possíveis tuplas de valores <strong>(x1, x2, x3, x4, y)</strong> com sua respectiva frequência absoluta (que é proporcional à probabilidade de obtenção da tupla). A simulação foi feita com 1024 <em>shots</em>. Repare que, de todas as <strong>2⁴</strong> tuplas, a que representa a solução do problema é a mais frequente. A ideia do terminador <em>amplify</em> é essa: amplificar as probabilidades das tuplas que satisfazem uma determinada condição.</p><h4>Exemplo 2 — fatoração prima em DLQ</h4><p>Segue agora um exemplo de código que resolve um problema de <strong>fatoração prima</strong>:</p><pre>p1[4] in {2, 3, 5, 7};<br>p2[4] in {2, 3, 5, 7};<br>y[1] := p1*p2=15;<br>amplify y 2 times</pre><p>Fatoração prima é um problema computacional que não tem solução eficiente conhecida na computação clássica. Este problema consiste em encontrar, para um número natural <strong>k</strong>, um par de números primos <strong>(p₁,p₂)</strong> tal que <strong>p₁p₂=k</strong>. Neste exemplo, considerou-se <strong>k=15</strong>.</p><p>No código acima, 3 variáveis são definidas: <strong>p1</strong>, <strong>p2</strong> e <strong>y</strong>. As duas primeiras variáveis são definidas como pertencentes ao conjunto dos números primos de 2 até 7. Ambas são de 4 <em>qubits</em>. Já a variável <strong>y</strong>, de 1 <em>qubit</em>, é definida como resultado da expressão <strong>p1*p2=15</strong>. Na última linha, o terminador <em>amplify</em> é aplicado com <strong>y</strong> como variável alvo e 2 como número de iterações.</p><p>Compilando e executando o código descrito acima, temos a seguinte tabela de resultados:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/361/1*OfsWYS9yFWn423ILkYcwiw.png" /><figcaption>Tabela de resultados da simulação do exemplo de fatoração prima em DLQ, usando o simulador aer_simulator, com 1024 shots de simulação</figcaption></figure><p>Como mostra a tabela acima, as tuplas <strong>(p1, p2, y)</strong> com maiores probabilidades de obtenção são as soluções <strong>(5, 3, 1)</strong> e <strong>(3, 5, 1)</strong>.</p><h4>Exemplo 3 — resolução de sistemas de equações</h4><p>Os exemplos 1 e 2 foram usados como prova de conceito em meu TCC. Outro exemplo que gostaria de ter usado é um código para resolver um sistema de equações. Porém, em todos os testes que fiz deste tipo de aplicação, as simulações requereram mais que 100% da memória RAM do meu computador. Um código para resolver, por exemplo, um sistema formado pelas equações lineares <strong>x+2y=5</strong> e <strong>3x-5y=4</strong>, ficaria da seguinte forma:</p><pre>x[2] in {0, 1, 2, 3};<br>y[2] in {0, 1, 2, 3};<br>s[1] := (x + 2*y = 5) and (3*x - 5*y = 4);<br>amplify s 3 times</pre><h3>O compilador DLQpiler</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/510/1*eS4V8T2V3xMiNlOiQzq6iA.png" /><figcaption>Um compilador é uma ferramenta que transforma código de alto nível de abstração em código intermediário ou código de máquina</figcaption></figure><p>O compilador que desenvolvi para a linguagem DLQ foi batizado como <em>DLQpiler</em>. O nome é uma brincadeira fonética com a palavra “<em>compiler</em>”, do inglês. Este compilador foi desenvolvido em Python, e os principais pacotes utilizados são o SDK de computação quântica Qiskit, da IBM, e a biblioteca PLY.</p><p>O processo de compilação de um código DLQ tem as 3 seguintes etapas:</p><ul><li><strong>análise léxica</strong>, na qual os lexemas da linguagem são identificados no código DLQ e sequenciados;</li><li><strong>análise sintática</strong>, na qual a sequência de lexemas é transformada em uma árvore sintática conforme a gramática da linguagem;</li><li><strong>síntese</strong>, na qual um circuito quântico é gerado a partir do processamento da árvore sintática.</li></ul><p>As 3 seguintes figuras ilustram os processos de análise léxica, análise sintática e síntese para o trecho de código <strong>“y[1] := p1*p2=15”</strong> (leia as legendas).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*65Tx_F9cSrRoGy3LeSyiiA.png" /><figcaption>Ilustração do processo de análise léxica. Neste processo, o analisador léxico identifica os lexemas da linguagem no texto de entrada, gerando uma lista de objetos chamados Tokens, que contêm fragmentos do texto com suas respectivas classificações conforme as gramáticas regulares da linguagem.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*enjA4A4VYzfAytzIvmsSZw.png" /><figcaption>Ilustração do processo de análise sintática. Neste processo, o analisador sintático gera uma árvore sintática de acordo com a gramática livre de contexto da linguagem. Cada nó da árvore sintática representa uma parte da estrutura do código, como um operador, um nome de variável, uma declaração, etc. Cada nível da árvore representa uma “frase” válida na linguagem.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ghXgb9SIt6zoGy9uQ6s0CA.png" /><figcaption>Ilustração do processo de síntese. Neste processo, uma análise recursiva em intra-ordem da árvore sintática é feita, gerando partes do circuito quântico final, unidas em seguido pelo módulo de síntese. Esta ilustração mostra um circuito quântico que resolve a expressão p1*p2=15. Isto é, no entanto, apenas uma pequena parte do circuito quântico completo gerado pelo compilador para um programa completo.</figcaption></figure><p>O bê-a-bá dos compiladores é o seguinte: a análise léxica é feita por um módulo do compilador chamado <strong>analisador léxico</strong>, ou simplesmente “<strong><em>lexer</em></strong>”. Este módulo identifica padrões nas <em>substrings</em> do código de entrada de acordo com uma tabela de expressões regulares (também conhecidas como <em>regexes</em>). Uma expressão regular é, a grosso modo, um formalismo usado na computação para descrever padrões em sequências de caracteres. Já a análise sintática é feita por um módulo <strong>analisador sintático</strong>, também chamado de “<strong><em>parser</em></strong>”. Este módulo gera uma árvore sintática seguindo as regras de uma <strong>gramática livre de contexto</strong>. Uma gramática livre de contexto é um tipo de gramática formal criado por Noam Chomsky que consiste em um conjunto de regras que definem como sequências de lexemas podem ser combinadas para formar “frases” válidas na linguagem. Não pretendo entrar em detalhes sobre teoria das linguagens formais aqui. Uma boa referência para quem tem interesse no assunto é o livro <em>Compilers</em>, citado na seção de sugestões de leitura.</p><p>Os módulos <em>lexer</em> e <em>parser</em> dos compiladores são, em geral, desenvolvidos com o auxílio de ferramentas como Lex e Yacc, que geram os algoritmos analisadores a partir das regras gramaticais da linguagem. No caso do compilador <em>DLQpiler</em>, utiliza-se o pacote Python Lex-Yacc (PLY), que é uma versão para Python das ferramentas Lex e Yacc.</p><p><strong>Este compilador é <em>open-source</em>. Seu código-fonte está disponível no seguinte repositório do Github: </strong><a href="https://github.com/FilipeChagasDev/dlqpiler"><strong>https://github.com/FilipeChagasDev/dlqpiler</strong></a></p><h3>Considerações finais</h3><p>Sobre o projeto: como TCC, deu muito certo. A banca avaliadora fez alguns apontamentos sobre pequenos detalhes a serem corrigidos na monografia, mas avaliou o trabalho com nota 10. Já como ferramenta de uso industrial, precisa melhorar. Há melhorias óbvias a serem feitas, como correções de <em>bugs</em> no compilador e adição de uma etapa de pré-processamento de código para remover comentários. Além disso, um detalhe que só percebi após terminar a primeira versão do projeto é que exigir que o programador DLQ defina explicitamente o tamanho de cada variável não é realmente necessário, pois o próprio compilador tem funções que calculam a quantidade necessária de <em>qubits</em> para armazenar o resultado de cada expressão. Algumas outras melhorias menos simples a serem feitas são:</p><ul><li>implementação de um sistema de tipos com mais tipos de dados além de números naturais, como inteiros, <em>float</em> e <em>bool</em>;</li><li>inclusão de mais operadores, como divisão inteira, módulo, absoluto, raiz e exponencial;</li><li>inclusão de recursos de programação funcional, como funções lambda, ternários, listas e operadores <em>map</em>, <em>reduce</em> e <em>filter</em>;</li><li>implementação de mais terminadores para aplicações como busca de máximo/mínimo, otimização combinatória e contagem de soluções.</li></ul><p>A implementação de mais terminadores criaria possibilidades muito interessantes de uso da DLQ. Uma das aplicações práticas que pensei para a linguagem, ainda quando estava idealizando ela, foi o treinamento de modelos de <em>machine learning</em>. Para aqueles que não têm familiaridade com <em>machine learning</em>: “treinar” um modelo consiste em encontrar os coeficientes que minimizam uma função <em>loss</em>. Isso poderia ser feito em DLQ se houvesse um terminador de busca de valor mínimo ou de otimização aproximada. Outro problema similar que poderia ser resolvido em DLQ se houvessem terminadores dessa natureza é a <strong>estimativa de máxima verossimilhança</strong>, que consiste em estimar valores para os parâmetros de um modelo estatístico que maximizem sua função de verossimilhança. Porém, como já disse, não vale a pena trabalhar com um escopo tão amplo em um TCC, e por isso implementei apenas o terminador <em>amplify</em> na versão 1 do <em>DLQpiler.</em></p><p>A computação quântica ainda é um grande “mato” a ser desbravado. Dentro desse “mato”, há uma infinidade de possibilidades e incertezas para a DLQ e para projetos similares. Uma das maiores dificuldades que enfrentei desenvolvendo a DLQ, e que, em geral, pesquisadores da área enfrentam, diz respeito ao “teto” da maturidade da própria computação quântica. Atualmente, há uma pequena quantidade de computadores quânticos experimentais em todo o mundo, que possuem poucos <em>qubits</em> e muito ruído (dão respostas muito fora do esperado), o que nos faz ainda muito dependentes de simuladores. No entanto, o tempo de computação e a quantidade de memória que um simulador requer crescem exponencialmente com a quantidade de <em>qubits</em> simulados, o que faz com que simulações de pouco mais de 40 <em>qubits</em> já sejam proibitivamente dispendiosas. Além disso, há uma incerteza sobre quais algoritmos quânticos vão funcionar bem ou mal a médio prazo. Um exemplo disso é o polêmico artigo de Stoudenmire e Waintal, disponibilizado no arXiv em março deste ano, intitulado “<em>Grover’s Algorithm Offers No Quantum Advantage</em>” [3], que foi rapidamente rebatido por Scott Aaronson em seu <em>blog</em>, com um <em>post</em> de título “<a href="https://scottaaronson.blog/?p=7143"><em>Of course Grover’s algorithm offers a quantum advantage!</em></a>” [4].</p><h3>Sugestões de leitura</h3><ul><li>Minha monografia, de título “<strong>DLQ — um projeto de linguagem de programação de alto nível de abstração para computação quântica</strong>”, disponível em &lt;<a href="http://bdm.ufmt.br/handle/1/3271">http://bdm.ufmt.br/handle/1/3271</a>&gt; e &lt;<a href="https://drive.google.com/file/d/1gVaXii_HbIioqHDdnCMnqPb3Z2me-j5c/view?usp=sharing">https://drive.google.com/file/d/1gVaXii_HbIioqHDdnCMnqPb3Z2me-j5c/view?usp=sharing</a>&gt;.</li><li>Livro <strong><em>Quantum Computation and Quantum Information</em></strong>, dos autores <strong>Michael Nielsen</strong> e <strong>Isaac Chuang. </strong>Essa obra é uma das principais referências em computação quântica (senão a principal). É um dos livros mais completos e detalhados da área.</li><li>Livro <strong><em>Quantum Computing for Computer Scientists</em></strong>, dos autores <strong>Noson Yanofskyn</strong> e <strong>Mirco Mannucci</strong>. Como o próprio nome sugere, é um livro de computação quântica para pessoas da computação.</li><li>Artigo <a href="https://quantum-journal.org/papers/q-2018-08-06-79/#"><strong><em>Quantum Computing in the NISQ era and beyond</em></strong></a>, do autor <strong>John Preskill</strong>: um artigo científico muito importante, publicado em 2018, que batiza a atual era da computação quântica como NISQ<em> (Noisy Intermediate-Scale Quantum era)</em>. É uma excelente leitura para entender os desafios da computação quântica nos dias de hoje.</li><li>Livro <strong><em>Compilers</em></strong>, dos autores <strong>Alfred Aho</strong>, <strong>Revi Sethi</strong> e <strong>Jeffrey Ullman </strong>— o famoso livro do dragão (dê uma olhada nas capas). Acredito que essa seja a obra mais usada como livro-texto das “cadeiras” de compiladores nas universidades. Você encontrará edições traduzidas desse livro com facilidade em bibliotecas universitárias.</li><li>Artigos do meu blog <a href="https://medium.com/cq-em-portugu%C3%AAs"><strong>CQ em Português</strong></a>, que criei para ser uma fonte de conteúdo didático em língua portuguesa sobre computação quântica.</li></ul><h3>Referências</h3><ol><li>GROVER, L. K. A fast quantum mechanical algorithm for database search. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing — STOC ’96, 1996</li><li>FARHI, E.; GOLDSTONE, J.; GUTMANN, S. A Quantum Approximate<br>Optimization Algorithm. arXiv, 2014. Disponível em &lt;https://arxiv.org/abs/1411.4028&gt;.</li><li>STOUDENMIRE, E. M.; WAINTAL, X. Grover’s Algorithm Offers No Quantum Advantage. <strong>arXiv:2303.11317 [cond-mat, physics:quant-ph]</strong>, 20 mar. 2023. Disponível em &lt;<a href="https://arxiv.org/abs/2303.11317">https://arxiv.org/abs/2303.11317</a>&gt;.</li><li><strong>Of course Grover’s algorithm offers a quantum advantage!</strong> Disponível em: &lt;<a href="https://scottaaronson.blog/?p=7143#:~:text=Grover&#39;s%20Algorithm%20Offers%20No%20Quantum%20Advantage&amp;text=It%20involves%20an%20%E2%80%9Coracle%E2%80%9D%20(,speedup%20guaranteed%20by%20the%20algorithm.">https://scottaaronson.blog/?p=7143#:~:text=Grover</a>&gt;. Acesso em: 16 jun. 2023.</li><li>VEDRAL, V.; BARENCO, A.; EKERT, A. Quantum networks for elementary arithmetic operations. <strong>Physical Review A</strong>, v. 54, n. 1, p. 147–153, 1 jul. 1996.</li><li>DRAPER, T. G. <strong>Addition on a Quantum Computer</strong>. Disponível em: &lt;https://arxiv.org/abs/quant-ph/0008033&gt;. Acesso em: 16 jun. 2023.</li><li>‌RUIZ-PEREZ, L.; GARCIA-ESCARTIN, J. C. Quantum arithmetic with the quantum Fourier transform. <strong>Quantum Information Processing</strong>, v. 16, n. 6, 28 abr. 2017.</li><li>BRASSARD, G.; HOYER, P.; TAPP, A. <strong>Quantum Counting</strong>. Disponível em: &lt;https://arxiv.org/abs/quant-ph/9805082&gt;. Acesso em: 16 jun. 2023.</li><li>DEUTSCH, D. Quantum theory, the church–turing principle and the universal quantum computer. Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, v. 400, n. 1818, p. 97–117, Jul 1985.</li><li>FEYNMAN, R. P. Simulating physics with computers. International Journal of Theoretical Physics, v. 21, n. 6–7, p. 467–488, 1982.</li><li>SHOR, P. W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, v. 26, n. 5, p. 1484–1509, 1997.</li></ol><h3>Citação</h3><p>Caso queira citar o projeto DLQ em um trabalho acadêmico, <strong>peço que não cite diretamente o presente artigo do Medium. Ao invés disso, cite minha monografia</strong>. Você pode citar no formato ABNT:</p><ul><li><strong>FERRAZ, Filipe Chagas. DLQ — projeto de linguagem de programação de alto nível de abstração para computação quântica. 2023. 136 f. Trabalho de Conclusão de Curso. (Graduação em Engenharia da Computação) — Universidade Federal de Mato Grosso. Faculdade de Engenharia, Cuiabá, 2023.</strong></li></ul><p>Ou no formato BibTeX, caso use LaTeX:</p><pre>@article{Ferraz_2023, <br>  title={Dlq - projeto de linguagem de programação de alto nível de abstração para computação quântica}, <br>  url={http://bdm.ufmt.br/handle/1/3271}, <br>  note={Accepted: 2023-07-11T22:32:06Z}, <br>  publisher={Universidade Federal de Mato Grosso}, <br>  author={Ferraz, Filipe Chagas}, <br>  year={2023}, <br>  month={Jun}, <br>  language={português} <br>}</pre><p>Pretendo escrever um artigo formal em inglês sobre a DLQ em breve para, pelo menos, deixar disponível no <strong>arXiv</strong>. Quanto este artigo estiver disponível, colocarei o <em>link </em>e as formas de citação aqui.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f11e96bd13ff" width="1" height="1" alt=""><hr><p><a href="https://medium.com/cq-em-portugu%C3%AAs/dlq-um-projeto-de-linguagem-de-programa%C3%A7%C3%A3o-para-computa%C3%A7%C3%A3o-qu%C3%A2ntica-f11e96bd13ff">DLQ — um projeto de linguagem de programação para computação quântica</a> was originally published in <a href="https://medium.com/cq-em-portugu%C3%AAs">CQ em Português</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[O “Hello World” da computação quântica]]></title>
            <link>https://medium.com/cq-em-portugu%C3%AAs/o-hello-world-da-computa%C3%A7%C3%A3o-qu%C3%A2ntica-d7ed4de6052c?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/d7ed4de6052c</guid>
            <category><![CDATA[ibm-quantum]]></category>
            <category><![CDATA[computação-quântica]]></category>
            <category><![CDATA[hello-world]]></category>
            <category><![CDATA[qiskit]]></category>
            <category><![CDATA[python]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Thu, 26 Jan 2023 04:33:16 GMT</pubDate>
            <atom:updated>2023-01-26T19:59:10.564Z</atom:updated>
            <content:encoded><![CDATA[<p>Nos artigos anteriores da CQ em Português (<a href="http://qubits/"><strong>Qubits </strong></a>e <a href="https://medium.com/cq-em-portugu%C3%AAs/portas-l%C3%B3gicas-qu%C3%A2nticas-ed014c43a381"><strong>Portas Lógicas Quânticas</strong></a>), foram apresentados alguns conceitos básicos e teóricos de computação quântica. Neste artigo, partiremos para uma abordagem mais prática, porém igualmente básica, com a linguagem <strong><em>Python </em></strong>e o SDK <strong>Qiskit</strong>. O exercício prático que aqui será lecionado é a geração de um <strong>estado Bell</strong>, que, como já explicado no artigo sobre <em>qubits</em>, é um estado de dois <em>qubits </em>emaranhados (Eq. 1).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/302/1*GDQI483vxsPdYntIRfsIGg.png" /><figcaption>Eq. 1 — Definição de um estado Bell</figcaption></figure><p>Um estado Bell pode ser gerado com uma porta Hadamard e uma porta Controlled-NOT, como mostra a figura a seguir:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/636/1*iBEP3TuDpyGVHiK5TKPyhw.png" /><figcaption>Fig. 1 — Circuito quântico que gera o estado Bell</figcaption></figure><p>Este circuito quântico pode ser representado algebricamente da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/341/1*GgqqFpxelF-s8-gCZsAPNg.png" /><figcaption>Eq. 2 — Representação algébrica reduzida do circuito quântico da fig. 1</figcaption></figure><p>onde <strong><em>Cx</em></strong> corresponde à porta <em>Controlled-NOT, </em><strong><em>H</em></strong> corresponde à porta <em>Hadamard</em> e <strong><em>I</em></strong> corresponde a uma matrix identidade 2x2.</p><h3>Implementação e simulação do circuito quântico da fig. 1 com Qiskit</h3><p>Qiskit é, atualmente, uma das principais ferramentas de desenvolvimento para computação quântica. Este poderoso SDK contém recursos para manipulação, transpilação, simulação e execução de algoritmos quânticos, além de incluir uma grande coleção de “<em>helpers</em>” para a implementação de algoritmos quânticos e híbridos de otimização, <em>machine learning</em>, aritmética, química, etc.</p><p>Qiskit é multiplataforma e seu processo de instalação é bastante simples, basta digitar “<em>pip install qiskit</em>” no terminal.</p><h4>Primeiro passo — importação do Qiskit</h4><p>Utilize o comando “<em>import qiskit</em>” para fazer com que os recursos da biblioteca Qiskit sejam carregados.</p><pre>import qiskit</pre><h4>Segundo passo — criação dos registradores</h4><p>Para esta prática, é necessário criar um registrador quântico de 2 <em>qubits </em>e um registrador clássico de 2 <em>bits</em>. Isto pode ser feito com o seguinte trecho de código:</p><pre>qr = qiskit.QuantumRegister(2)<br>cr = qiskit.ClassicalRegister(2)</pre><h4>Terceiro passo — construção do circuito quântico</h4><p>Para construir o circuito quântico apresentado na fig. 1, é necessário, primeiro, criar um objeto <em>QuantumCircuit </em>com os dois registradores inclusos.</p><pre>qc = qiskit.QuantumCircuit(qr, cr)</pre><p>Após criar o objeto <em>QuantumCircuit</em>, utilize os métodos <strong><em>h</em></strong> e <strong><em>cx</em></strong> para adicionar as portas <em>Hadamard </em>e <em>Controlled-NOT</em> ao circuito.</p><pre>qc.h(qr[0]) #Adiciona uma porta Hadamard sobre o qubit 0<br>qc.cx(qr[0], qr[1]) #Adiciona uma porta Controlled-NOT com o qubit 0 como controle e o qubit 1 como alvo</pre><p>Para completar a construção do circuito, é necessário adicionar portas de medição. Estas portas são responsáveis por medir o estado do registrador quântico e armazenar o resultado no registrador clássico (lembre-se do que foi dito sobre colapso de estado quântico no artigo sobre <em>qubits</em>). Para adicionar estas portas, utilize o método <strong><em>measure</em></strong>.</p><pre>qc.measure(qr, cr)</pre><p>É possível visualizar o circuito construído com o método <strong><em>draw</em></strong>. Caso tenha a biblioteca <strong><em>matplotlib</em></strong> instalada, utilize o seguinte trecho de código:</p><pre>import matplotlib.pyplot as plt<br><br>qc.draw(output=&#39;mpl&#39;)<br>plt.show()</pre><p>O resultado é esta figura:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/472/1*Pt8YxMLWL3XhfyiHRJK_kA.png" /><figcaption>Fig. 2 — Circuito construído com Qiskit</figcaption></figure><h4>Quarto passo — simulação</h4><p>O SDK Qiskit possui um simulador chamado <strong><em>Aer</em></strong>. Há um pequeno conjunto de métodos de simulação disponíveis no <strong><em>Aer</em></strong>, cada um com suas vantagens e desvantagens. Para esta prática, escolhi o método <strong><em>statevector</em></strong>.</p><p>Para carregar o simulador, utilize a seguinte linha de código:</p><pre>sim = qiskit.Aer.get_backend(&#39;aer_simulator_statevector&#39;)</pre><p>Para executar a simulação, utilize o método <strong><em>run</em></strong> do simulador. Este método irá retornar um objeto <strong><em>AerJob</em></strong>.</p><pre>job = sim.run(qc, shots=1024)</pre><p>Observe que há um argumento “<strong><em>shots</em></strong>” no método <strong><em>run</em></strong>. Este argumento especifica a quantidade de vezes que o circuito quântico é executado.</p><p>Para obter os resultados da simulação, utilize o método <strong><em>result </em></strong>da classe <strong><em>AerJob.</em></strong> Este método retorna um objeto <strong><em>Result</em></strong> contendo várias informações sobre a simulação.</p><pre>res = job.result()</pre><p>Para obter as medições do estado final do circuito quântico, utilize o método <strong><em>get_counts</em></strong> da classe <strong><em>Result</em></strong>. Este método retorna um <em>dict</em> contendo as <em>bit-strings</em> obtidas na simulação, cada uma com a respectiva frequência.</p><pre>counts = res.get_counts()<br><br>print(counts)<br>#Saída: {&#39;00&#39;: 530, &#39;11&#39;: 494}</pre><p>Observe que, nesta simulação, a sequência de bits “00” foi obtida 530 vezes e a sequência “11” foi obtida 494 vezes.</p><p>Utilizando a biblioteca <em>Matplotlib</em> (já importada) e a função <strong><em>plot_histogram</em></strong> do Qiskit, é possível transformar este <em>dict</em> em um histograma.</p><pre>from qiskit.tools.visualization import plot_histogram<br><br>plot_histogram(counts)<br>plt.show()</pre><p>O resultado é a seguinte figura:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*SozCTK6FIW5-NyKbZfAWAw.png" /></figure><h4>Interpretação do resultado</h4><p>O estado Bell é formado por uma combinação linear de dois estados puros: <em>|00&gt;</em> e <em>|11&gt;</em>. Teoricamente, as probabilidades do estado Bell colapsar em <em>|00&gt;</em> e <em>|11&gt;</em> são iguais, ou seja, ambas <em>1/2</em>. Na simulação, as frequências relativas obtidas foram <em>530/1024=0.52</em> e <em>494/1024=0.48</em>. Pela lei dos grandes números, quanto maior for a quantidade de <em>shots</em> de simulação, mais próximas de <em>1/2</em> serão estas frequências relativas obtidas. No entanto, vale ressaltar que o método de simulação <em>statevector</em> é <strong>ideal</strong>, ou seja, não considera o ruído de um computador quântico real.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d7ed4de6052c" width="1" height="1" alt=""><hr><p><a href="https://medium.com/cq-em-portugu%C3%AAs/o-hello-world-da-computa%C3%A7%C3%A3o-qu%C3%A2ntica-d7ed4de6052c">O “Hello World” da computação quântica</a> was originally published in <a href="https://medium.com/cq-em-portugu%C3%AAs">CQ em Português</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Portas Lógicas Quânticas]]></title>
            <link>https://medium.com/cq-em-portugu%C3%AAs/portas-l%C3%B3gicas-qu%C3%A2nticas-ed014c43a381?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/ed014c43a381</guid>
            <category><![CDATA[porta-lógica]]></category>
            <category><![CDATA[computação]]></category>
            <category><![CDATA[computação-quântica]]></category>
            <category><![CDATA[quântica]]></category>
            <category><![CDATA[matemática]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Sun, 07 Feb 2021 10:06:05 GMT</pubDate>
            <atom:updated>2021-02-16T22:11:56.993Z</atom:updated>
            <content:encoded><![CDATA[<h4>O análogo das portas lógicas digitais na computação quântica</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YTS5kMT7YJ_RiC_pfqeB2Q.png" /></figure><p>Dando continuidade ao texto <a href="https://medium.com/cq-em-portugu%C3%AAs/do-bit-ao-qubit-113975dca0f9"><em>Qubits — O (primeiro) princípio da computação quântica</em></a>, serão abordadas aqui as <strong>portas lógicas quânticas</strong>, responsáveis por modificar e emaranhar os estados dos qubits.</p><h3>Introdução</h3><h4>Portas lógicas clássicas e circuitos lógicos</h4><p>Uma porta lógica clássica é um dispositivo (normalmente eletrônico) com um conjunto de bits de entrada e um bit de saída. Este dispositivo implementa alguma lógica de “uns” e “zeros” para determinar o estado do bit de saída a partir dos estados dos bits de entrada.</p><p>As quatro principais portas lógicas clássicas são: NOT, OR, AND e XOR.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/272/1*85vkVEGwdCEfooQEBSXq0w.gif" /><figcaption>Simulação das portas lógica NOT, OR, AND e XOR.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1004/1*KJbKUF1-qwzgMR3vnXHLug.png" /><figcaption>Tabelas-verdade das portas lógicas NOT, OR, AND e XOR.</figcaption></figure><p>Combinando portas lógicas clássicas, é possível criar autômatos e circuitos lógicos capazes de realizar cálculos. O processador de um computador clássico, por exemplo, é composto em sua maior parte por portas lógicas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/1*n7Sve-em0yPIA-EIDPiyGw.gif" /><figcaption>Circuito lógico somador incompleto simples</figcaption></figure><h4>Circuitos quânticos</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/640/1*7f7BvviDb551nIyLV0yA9A.png" /><figcaption>Exemplo de circuito quântico</figcaption></figure><p><strong>Circuitos quânticos</strong> são diagramas que costumam ser usados como pseudocódigo para algoritmos quânticos. Neles, os qubits são representados como linhas horizontais, e as “portas lógicas quânticas” — ou melhor dizendo, os operadores análogos às portas lógicas digitais na computação quântica — são representadas como pequenos retângulos desenhados sobre as linhas horizontais, as vezes acompanhados de linhas verticais que os ligam a qubits de controle. O percurso da esquerda para a direita das linhas horizontais representa a evolução temporal do sistema.</p><h4>O que de fato são as “portas lógicas quânticas”</h4><p>As tais portas lógicas quânticas são, na verdade, operadores lineares unitários (matrizes). Então, convém prosseguir com esta leitura fazendo uma breve abordagem de álgebra linear. Em seguida, serão apresentadas as principais portas lógicas quânticas e suas respectivas funções dentro dos circuitos quânticos.</p><h3>Conceitos de álgebra linear</h3><h4>Mapas/Transformações e Operadores Lineares [1]</h4><p><strong>Mapas lineares</strong>, também conhecidos como <strong>transformações lineares, aplicações lineares</strong> e, em alguns casos,<strong> operadores lineares, </strong>são funções que possuem as seguintes propriedades:</p><ul><li><strong>F(𝑏+𝑐) = F(𝑏) + F(𝑐)</strong>, onde 𝑏 e 𝑐 pertencem ao domínio de F.</li><li><strong>F(λ𝑏) = λF(𝑏)</strong>, onde λ é uma constante.</li></ul><p>Uma matriz <strong>A</strong> de<strong> 𝑛 </strong>linhas e<strong> 𝑚 </strong>colunas é um mapa linear tal que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/287/1*zB-m-9aK8Ry8JoCLyZRghA.png" /><figcaption>(1)</figcaption></figure><p>onde:</p><ul><li><strong>K</strong> é um <strong>corpo, </strong>um tipo especial de conjunto numérico. Na computação quântica, este <strong>K</strong> costuma ser ℂ (o conjunto dos complexos).</li><li><strong>Kᵐ</strong> e <strong>Kⁿ</strong> são espaços vetoriais de, respectivamente, 𝑚 e 𝑛 dimensões.</li><li><strong>𝑣 </strong>é um vetor pertencente ao espaço vetorial <strong>Kᵐ</strong></li><li><strong>A𝑣</strong> (o produto da matriz <strong>A</strong> pelo vetor <strong>𝑣</strong>) é um vetor pertencente ao espaço vetorial <strong>Kⁿ</strong></li></ul><p>Traduzindo da linguagem matemática para o bom português: o produto da matriz <strong>A</strong> pelo vetor <strong>𝑣 ∊ Kᵐ</strong> resulta em um vetor <strong>A𝑣</strong> (que chamaremos de <strong>𝑢</strong>) tal que <strong>𝑢 ∊ Kⁿ</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/452/1*xjuljiKVnRX_iwdrpmjfpg.png" /><figcaption>(2)</figcaption></figure><p>A matriz <strong>A</strong>, como um mapa linear,<strong> </strong>tem as seguintes propriedades:</p><ul><li><strong>A(𝑏+𝑐) = A𝑏 + A𝑐</strong>, onde <strong>𝑏,𝑐 ∊ Kᵐ</strong></li><li><strong>A(λ𝑏) = λA(𝑏)</strong>, onde <strong>𝑏 ∊ Kᵐ</strong> e <strong>λ∊ K</strong></li></ul><p>Duas matrizes <strong>A</strong> e <strong>B</strong> de <strong>𝑛 </strong>linhas e<strong> 𝑚 </strong>colunas têm as seguintes propriedades:</p><ul><li><strong>(A+B)(𝑐) = Ac + Bc</strong>, onde <strong>𝑐 ∊ Kᵐ</strong></li><li><strong>(A+B)(𝑏+𝑐) = A(𝑏+𝑐) + B(𝑏+𝑐) = A𝑏 + A𝑐 + B𝑏 + B𝑐</strong>, onde <strong>𝑏,𝑐 ∊ Kᵐ</strong></li><li><strong>(A+B)(λ𝑐) = A(λ𝑐) + B(λ𝑐) = λA𝑐 + λB𝑐, </strong>, onde <strong>𝑐 ∊ Kᵐ</strong> e <strong>λ∊ K</strong></li></ul><p>Um mapa linear pode ser chamado de <strong>operador linear</strong> quando seu conjunto domínio equivale ao seu contradomínio.</p><h4>Matriz identidade</h4><p>Uma matriz de<strong> 𝑛 </strong>linhas e<strong> 𝑛 </strong>colunas cujas entradas da diagonal principal são <strong>1</strong> e todas as outras entradas são <strong>0</strong> é denominada <strong>matriz identidade</strong> e costuma ser denotada por <strong>Iₙ</strong> (ou simplesmente <strong>I</strong>, caso o número de linhas e colunas já esteja claro no contexto). <strong>[6]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/291/1*ZDGuQAKqGkzWht47pOzewg.png" /><figcaption>Forma geral de uma matriz identidade</figcaption></figure><p>Este tipo de matriz é especial pela seguinte propriedade: para qualquer matriz <strong>A</strong> de <strong>𝑚</strong> linhas e <strong>𝑛</strong> colunas, temos que <strong>Iₘ A = A Iₙ = A</strong>. <strong>[7]</strong></p><p>Esta primeira propriedade implica nas seguintes:</p><ul><li>Para qualquer matriz coluna <strong>𝑣 </strong>de<strong> 𝑛 </strong>entradas:<strong> Iₙ 𝑣 = 𝑣</strong>.</li><li>Para qualquer matriz linha <strong>𝑢</strong> de<strong> 𝑛 </strong>entradas:<strong> 𝑢 Iₙ = 𝑢</strong>.</li><li>Para qualquer matriz <strong>A</strong> de<strong> 𝑛 </strong>linhas e<strong> 𝑛 </strong>colunas:<strong> Iₙ A = A Iₙ = A</strong>.</li></ul><p>Como, tratando-se de mapas lineares, é de costume representar vetores como matrizes coluna, é assumido que uma matriz identidade <strong>I</strong> é um operador linear que não altera o operando (tal como a função <strong>𝑓(𝑥)=𝑥</strong>).</p><h4>Matriz transposta e transposta conjugada</h4><p>A grosso modo, a <strong>transposição</strong> de uma matriz de números reais é uma operação na qual as linhas da matriz são transformadas em colunas e as colunas são transformadas em linhas.</p><p>Considere uma matriz de números reais <strong>A</strong> de <strong>𝑛 </strong>linhas e<strong> 𝑚 </strong>colunas. Sua transposta <strong>Aᵀ</strong> é uma matriz de <strong>𝑚 </strong>linhas e<strong> 𝑛 </strong>colunas cujas entradas <strong>Aᵀ₍ⱼ,ₖ₎</strong> (sendo 𝑗 o índice linha e 𝑘 o índice coluna) satisfazem à equivalência <strong>Aᵀ₍ⱼ,ₖ₎=A₍ₖ,ⱼ₎</strong>. <strong>[1]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/210/1*uPBmHsE0MoFfIt4L61IIhA.png" /><figcaption>Exemplo de transposição de uma matriz de números reais</figcaption></figure><p>Tratando-se de matrizes de números complexos, existem também as <strong>transpostas conjugadas</strong>, nas quais, além da inversão linha-coluna, há a “conjugação” das entradas. <strong>[2]</strong> Quando a matriz de números complexos é um operador linear, sua transposta conjugada é também conhecida como <strong>operador adjunto hermitiano</strong>. <strong>[8][10]</strong></p><p>Basicamente, o conjugado de um número complexo <strong>𝑧=α+iβ</strong> é <strong>𝑧*=α-iβ</strong> (repare na inversão do sinal da parte complexa).</p><p>Diferente da transposta simples, que é simbolizada pela letra ‘ T ’ sobrescrita, a transposta conjugada é representada pelo símbolo <em>Dagger</em> (‘ † ’) sobrescrito ou por um asterísco (‘ * ‘).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/434/1*GNpCyB2dw6weel3uNHohCA.png" /><figcaption>Exemplo de transposta conjugada</figcaption></figure><h4>Funções e Matrizes inversas</h4><p>Considere uma função injetora <strong>𝑓:X⟼Y </strong>(sendo <strong>X</strong> seu conjunto domínio e <strong>Y</strong> seu contradomínio). A função inversa de <strong>𝑓</strong> é uma função <strong>𝑔:Y⟼X</strong> tal que, para <strong>𝑥∊X </strong>e <strong>𝑦∊Y</strong>, se é verdade que <strong>𝑦=𝑓(𝑥),</strong> é também verdade que <strong>𝑥=𝑔(𝑦)</strong>, ou seja:<strong> 𝑔(𝑓(𝑥))=𝑥</strong>. <strong>[3]</strong></p><p>Por exemplo: as funções<strong> 𝑓(𝑥)=2𝑥</strong> e<strong> 𝑔(𝑥)=𝑥/2</strong> são inversas, pois <strong>𝑓(𝑔(𝑥))=2(𝑥/2)=(2/2)𝑥=𝑥</strong>.</p><p>Funções inversas são frequentemente denotadas pelo número “<strong>-1</strong>” sobrescrito. A inversa de <strong>𝑓(𝑥)</strong>, por exemplo, pode ser denotada por <strong>𝑓 ⁻¹(𝑥)</strong>. No entanto esta é uma notação confusa, pois o “<strong>-1</strong>” sobrescrito também pode denotar uma potência, e <strong>𝑓 </strong>elevado a <strong>-1</strong> não necessariamente equivale à inversa de <strong>𝑓</strong>. <strong>[3]</strong></p><p><strong>Matriz inversa</strong> é, basicamente, uma forma matricial de <strong>função inversa</strong>.</p><p>Considere uma matriz quadrada <strong>A</strong>. Sua inversa é uma matriz <strong>A⁻¹</strong> tal que, se é verdade que <strong>𝑢=A𝑣</strong>, também é verdade que<strong> 𝑣=A⁻¹𝑢</strong>, ou seja, <strong>𝑣=AA⁻¹𝑣</strong>.</p><p>Partindo do pressuposto de que uma matriz identidade <strong>I</strong> com as mesmas quantidades de linhas e colunas que <strong>AA⁻¹ </strong>satisfaz <strong>𝑣=I𝑣</strong>, conclui-se que <strong>AA⁻¹=I</strong>. Portanto, para provar que uma matriz <strong>B</strong> é inversa de <strong>A</strong>, basta mostrar que <strong>AB=I</strong>.<strong> [1][4]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/680/1*rolayqu42SIivGhRcI9sZA.png" /><figcaption>Exemplo de inversão de matrizes</figcaption></figure><h4>Matriz unitária [5]</h4><p>Uma matriz quadrada <strong>U</strong> (que tem a mesma quantidade de linhas e colunas) é dita unitária quando sua transposta conjugada é também sua inversa.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/119/1*x5RfaXJRryviMjdUIrC8Vw.png" /><figcaption>Principal propriedade de uma matriz unitária</figcaption></figure><p>É possível verificar se uma matriz quadrada <strong>U</strong> é unitária de duas formas:</p><ul><li>Se <strong>|det U|=1</strong>, então a matriz <strong>U</strong> é unitária.</li><li>Se <strong>UU*=I</strong>, então a matriz <strong>U</strong> é unitária.</li></ul><p>Uma matriz unitária é um mapa linear que caracteriza-se por não alterar a norma do vetor operando (<strong>|U𝑣|=|𝑣|</strong>).</p><p>Todos os operadores lineares usados em algoritmos quânticos são unitários.</p><h4>Operadores autoadjuntos</h4><p>Um operador linear <strong>A</strong> atuando em um espaço de Hilbert é dito <strong>autoadjunto</strong> quando satisfaz a regra <strong>⟨A𝑢|𝑣⟩=⟨𝑢|A𝑣⟩</strong> para qualquer par <strong>𝑢,𝑣</strong>. <strong>[11]</strong></p><p>Quando o operador linear é uma matriz quadrada, ele também se caracteriza por equivaler ao seu próprio adjunto hermitiano. <strong>[12]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/88/1*MlUDds5vLaGqFl4XFLgeaA.png" /><figcaption>Operador autoadjunto matricial A</figcaption></figure><p>Alguns dos operadores lineares usados em algoritmos quânticos são autoadjuntos.</p><h3>Operadores de 1 qubit</h3><p>Aqui começa a abordagem sobre as “portas lógicas quânticas” (ou melhor dizendo, os operadores básicos da computação quânticas). Primeiramente, serão apresentadas 9 portas de 1 qubit: Pauli-X, Pauli-Y, Pauli-Z, Rx, Ry, Rz, Hadamard, Phase e π/8. Em seguida, na próxima seção, serão apresentadas 4 portas de múltiplos qubits: Controlled-NOT, Swap, Controlled-U e Toffoli. Estas são apenas algumas das portas lógicas quânticas existentes. É possível criar uma infinidade de outras portas lógicas quânticas a partir destas mais básicas.</p><h4>Pauli-X, Pauli-Y e Pauli-Z</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/380/1*Qdqo8VT3J37MnnIs_lNOYA.png" /><figcaption>Símbolos das portas lógicas quânticas Pauli-X, Pauli-Y e Pauli-Z na plataforma IBM QX Circuit Composer.</figcaption></figure><p>Os operadores Pauli-X, Pauli-Y e Pauli-Z são responsáveis por rotacionar o estado de um qubit em 180 graus na esfera de Bloch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/481/1*ItEi_M7SpLD46glEzRKqbQ.png" /><figcaption>Definição dos operadores Pauli-X, Pauli-Y e Pauli-Z. <strong>[13]</strong></figcaption></figure><p>Os nomes dos operadores já sugerem o eixo de rotação de cada um: Pauli-X rotaciona em torno do eixo <strong>x</strong>, Pauli-Y rotaciona em torno do eixo <strong>y</strong> e Pauli-Z rotaciona em torno do eixo <strong>z</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/551/1*pn4iwGPyhA3FASHU6zszEg.png" /><figcaption>Ilustração das transformações Pauli-X, Pauli-Y e Pauli-Z na esfera de Bloch.</figcaption></figure><p>O operador Pauli-X pode ser interpretado como uma “versão quântica” da porta lógica NOT, pois:</p><ul><li><strong>X|0⟩ = |1⟩</strong></li><li><strong>X|1⟩ = |0⟩</strong></li></ul><p>Os três operadores Pauli são autoadjuntos.</p><h4>Rotações Rx, Ry e Rz.</h4><p>Os operadores Rx, Ry e Rz rotacionam o estado de um qubit em um angulo “<strong>θ”</strong> qualquer na esfera de Bloch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/541/1*Y32G_Y12_W4MOZAV7vmklg.png" /><figcaption>Definições dos operadores Rx, Ry e Rz. <strong>[13]</strong></figcaption></figure><p>Rx rotaciona em torno do eixo <strong>x</strong>, Ry rotaciona em torno do eixo <strong>y</strong> e Rz rotaciona em torno do eixo <strong>z</strong>.</p><p>Estes operadores não necessariamente são autoadjuntos. As inversas de <strong>Rx(θ), Ry(θ)</strong> e <strong>Rz(θ)</strong> são, respectivamente, <strong>Rx(-θ), Ry(-θ)</strong> e <strong>Rz(-θ).</strong></p><h4>Hadamard</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/124/1*4xnKlp_U942CfHeiejs2Lg.png" /><figcaption>Símbolo da porta lógica quântica Hadamard na plataforma IBM QX Circuit Composer.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/177/1*A7neJn4piKEW2cnZZfZuEQ.png" /><figcaption>Definição do operador Hadamard. <strong>[13]</strong></figcaption></figure><p>O operador Hadamard, denotado pela letra ‘H’, é um operador autoadjunto que pode ser usado para transformar estados não superpostos em estados superpostos (e vice-versa), como mostram os exemplos a seguir.</p><ul><li><strong>H|0⟩ = (|0⟩+|1⟩)/√2</strong></li><li><strong>H|1⟩ = (|0⟩-|1⟩)/√2.</strong></li><li><strong>H(|0⟩+|1⟩)/√2 = |0⟩</strong></li><li><strong>H(|0⟩-|1⟩)/√2 = |1⟩</strong></li></ul><p>O operador Hadamard pode ser definido alternativamente como <strong>H=(X+Z)/√2</strong>.<strong> [13]</strong></p><h4>Phase</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/113/1*uHQisN-evJ9O6bd0RxkppA.png" /><figcaption>Símbolo da porta lógica quântica S (Phase) na plataforma IBM QX Circuit Composer.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/131/1*rDL_Jy6Z-FYN_xsPADplCg.png" /><figcaption>Definição do operador S. [13]</figcaption></figure><p>O operador Phase (denotado pela letra <strong>S</strong>) aplica um fator de fase <strong>𝑖</strong> ao estado <strong>|1⟩</strong>. Seu uso tem o mesmo efeito de uma uma transformação <strong>Rz(π/2)</strong>. <strong>[14]</strong></p><ul><li><strong>S|0⟩ = |0⟩</strong></li><li><strong>S|1⟩ = 𝑖|1⟩</strong></li></ul><p><strong>S</strong> não é autoadjunto, sua função inversa é o operador <strong>S*</strong> (transposta conjugada de <strong>S</strong>).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/107/1*L4WxyqyS4ZnCKBQz041r-A.png" /><figcaption>Símbolo da porta lógica quântica S* (transposta conjugada de S) na plataforma IBM QX Circuit Composer.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/138/1*YQlF64HwR7WS0d0ElKyg8g.png" /><figcaption>Definição do operador S*.</figcaption></figure><h4>π/8</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/114/1*ZJ6XF3_Aoib0bNkAcsUWBg.png" /><figcaption>Símbolo da porta lógica quântica T (π/8) na plataforma IBM QX Circuit Composer.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/235/1*ZUUWCeaae9KSBbZQv_NDUA.png" /><figcaption>Definição do operador T. [13]</figcaption></figure><p>O operador π/8 (denotado pela letra <strong>T</strong>) aplica um fator de fase <strong>exp(𝑖π/4)</strong> ao estado <strong>|1⟩</strong>. Seu uso tem o mesmo efeito de uma uma transformação <strong>Rz(π/4)</strong>.</p><ul><li><strong>T|0⟩ = |0⟩</strong></li><li><strong>T|1⟩ = exp(𝑖π/4)|1⟩</strong></li></ul><p>Este operador é referido como π/8 simplesmente porque pode ser definido alternativamente como uma matriz com <strong>exp(±𝑖π/8)</strong> nas entradas da diagonal principal e com um fator global de fase <strong>exp(𝑖π/8)</strong>. <strong>[13]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/427/1*6VtjMt6xrbXWpFm_zVq_4A.png" /><figcaption>Definição do operador <strong>T</strong> com fator global de fase <strong>exp(𝑖π/8)</strong>.</figcaption></figure><p><strong>T </strong>não é autoadjunto, sua função inversa é o operador <strong>T*</strong> (transposta conjugada de <strong>T</strong>). <strong>[15]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/111/1*mAuzOZ8SmdvwZeEAAEcqzA.png" /><figcaption>Símbolo da porta lógica quântica T* (transposta conjugada de T) na plataforma IBM QX Circuit Composer.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/202/1*jESJZr5WxHhtT8JcZNMdGQ.png" /><figcaption>Definição do operador T* (transposta conjugada de T).</figcaption></figure><h3>Operadores de múltiplos qubits</h3><h4>Controlled-NOT</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/111/1*eJmJz1NnkWYruOJ5biyDMw.png" /><figcaption>Símbolo da porta lógica quântica Controlled-NOT na plataforma IBM QX Circuit Composer. Os qubits de controle e alvo são, respectivamente, q0 e q1.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/124/1*J85Zavm-dwhbtQps6ej_rg.png" /><figcaption>Definição do operador Controlled-NOT. <strong>[13]</strong></figcaption></figure><p>Controlled-NOT é o mais básico dos operadores de múltiplos qubits. Este possui dois operandos: um qubit de controle e um qubit alvo. Em termos de bases computacionais, seu comportamento pode ser definido da seguinte forma:</p><ul><li><strong>|𝑐⟩|𝑡⟩ </strong>⟼<strong>|𝑐⟩|𝑐 ⊕ 𝑡⟩</strong>, onde <strong>𝑐 </strong>e <strong>𝑡 </strong>são, respectivamente, <em>control</em> (controle) e <em>target</em> (alvo), e “⊕” é uma adição módulo 2, equivalente ao operador booleano XOR . <strong>[13]</strong></li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/202/1*cFC3sHc29XXTi3F7QAaOZQ.png" /><figcaption>Entradas e saídas da porta lógica quântica Controlled-NOT</figcaption></figure><p>Basicamente, o operador Controlled-NOT inverte o estado do qubit alvo quando o qubit de controle é definido como <strong>|1⟩</strong>. Quando o qubit de controle é definido como <strong>|0⟩</strong>, o estado do qubit alvo não sofre alteração. Em ambos os casos, o estado do qubit de controle não sofre alteração.<strong>[13]</strong></p><p>É possível explicar este comportamento usando uma analogia com o operador <em>if</em> ternário de uma linguagem de programação, como mostra o exemplo a seguir:</p><ul><li><strong>|𝑐⟩|𝑡⟩ </strong>⟼ <strong>|𝑐⟩|<em>not</em> 𝑐 <em>if</em> 𝑡 == 1 <em>else</em> c⟩</strong></li></ul><p>Obs: Neste exemplo eu usei especificamente a sintaxe do <em>if</em> ternário da linguagem Python.</p><p>No geral, o operador Controlled-NOT tende a apresentar o comportamento de um operador Pauli-X aplicado ao qubit alvo quando o qubit de controle colapsa em <strong>|1⟩</strong>.</p><p>O operador Controlled-NOT é autoadjunto.</p><h4>Swap</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/118/1*nHEo3_hWA1GJ47PFVK_Oww.png" /><figcaption>Símbolo da porta lógica quântica Swap na plataforma IBM QX Circuit Composer.</figcaption></figure><p>Swap é um operador composto por um arranjo de 3 operadores Controlled-NOT. Sua função é, basicamente, permutar os estados do par de qubits operandos.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/292/1*vLFjxCWJfLWF9vplQXOQhQ.png" /><figcaption>Composição de um operador Swap usando 3 operadores Controlled-NOT. O sistema inicia no estado <strong>|ψ⟩</strong>⊗<strong>|ɸ⟩</strong> e termina no estado <strong>|ɸ⟩</strong>⊗<strong>|ψ⟩, </strong>graças a permutação aplicada pelo operador Swap. <strong>[16]</strong></figcaption></figure><p>O comportamento do operador Swap pode ser definido da seguinte forma:</p><ul><li><strong>|ψ⟩|ɸ⟩ </strong>⟼ <strong>|ɸ⟩|ψ⟩</strong></li></ul><p>O operador Swap é autoadjunto.</p><h4>Controlled-U</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/184/1*XeLGH_dkSrRYI3GIPbDp6w.png" /><figcaption>Símbolo de um operador Controlled-U</figcaption></figure><p>Controlled-U é uma generalização para os diversos operadores controlados que podem ser criados a partir do operador Controlled-NOT e dos operadores de 1 qubit. <strong>[13]</strong> Basicamente, para um operador unitário <strong>U</strong> de 1 qubit, pode haver uma versão controlada, que atua como <strong>U</strong> sobre o qubit alvo apenas quando o qubit de controle colapsa em <strong>|1⟩.</strong></p><h4>Toffoli</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/117/1*XRYAuoYFrVCSlXxkno3j1g.png" /><figcaption>Símbolo da porta lógica quântica Toffoli na plataforma IBM QX Circuit Composer. Os dois qubits de controle e o qubit alvo são, respectivamente, q0, q1 e q2.</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/250/1*Ng9xmxtULJbxmiA-tPdb-Q.png" /><figcaption>Definição do operador Toffoli. <strong>[17]</strong></figcaption></figure><p>Toffoli é um operador que funciona de forma parecida com o Controlled-NOT, porém com dois qubits de controle.</p><p>Em termos de bases computacionais, o operador Toffoli inverte o estado do qubit alvo apenas quando ambos os qubits de controle são definidos como <strong>|1⟩. [13]</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/416/1*Y0W4IB1Wfr5hTrmk7JlbIg.png" /><figcaption>Tabela-verdade e simbologia de uma porta lógica quântica Toffoli. <strong>[13]</strong></figcaption></figure><p>Este comportamento pode ser definido da seguinte forma:</p><ul><li><strong>|𝑐₁⟩|𝑐₂⟩|𝑡⟩ </strong>⟼<strong>|𝑐₁⟩|𝑐₂⟩|𝑐₁𝑐₂ ⊕ 𝑡⟩</strong>, onde <strong>𝑐₁</strong>, <strong>𝑐₂ </strong>e <strong>𝑡 </strong>são, respectivamente, controle 1, controle 2, e <em>target</em> (alvo).</li></ul><p>A porta lógica quântica Toffoli pode ser implementada como um circuito quântico composto por portas de 1 e 2 qubits, como mostra a seguinte ilustração:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/619/1*xB0DXlaqI_rAo9BjAGX7jQ.png" /><figcaption>Implementação da porta lógica quântica Toffoli <strong>[13]</strong></figcaption></figure><p>O operador Toffoli é autoadjunto.</p><h3>Referências</h3><p>[1] LIESEN, Jörg; MEHRMANN, Volker. Linear Algebra. [S. l.]: Springer International Publishing, 2015. DOI 10.1007/978–3–319–24346–7. Disponível em: <a href="http://dx.doi.org/10.1007/978-3-319-24346-7.">http://dx.doi.org/10.1007/978-3-319-24346-7.</a></p><p>[2] <a href="https://mathworld.wolfram.com/about/author.html">Weisstein, Eric W.</a> “Conjugate Transpose.” From <a href="https://mathworld.wolfram.com/"><em>MathWorld</em></a> — A Wolfram Web Resource. <a href="https://mathworld.wolfram.com/ConjugateTranspose.html">https://mathworld.wolfram.com/ConjugateTranspose.html</a></p><p>[3] <a href="https://mathworld.wolfram.com/about/author.html">Weisstein, Eric W.</a> “Inverse Function.” From <a href="https://mathworld.wolfram.com/"><em>MathWorld</em></a> — A Wolfram Web Resource. <a href="https://mathworld.wolfram.com/InverseFunction.html">https://mathworld.wolfram.com/InverseFunction.html</a></p><p>[4] <a href="https://mathworld.wolfram.com/topics/Stover.html">Stover, Christopher</a> and <a href="https://mathworld.wolfram.com/about/author.html">Weisstein, Eric W.</a> “Matrix Inverse.” From <a href="https://mathworld.wolfram.com/"><em>MathWorld</em></a> — A Wolfram Web Resource. <a href="https://mathworld.wolfram.com/MatrixInverse.html">https://mathworld.wolfram.com/MatrixInverse.html</a></p><p>[5] <a href="https://mathworld.wolfram.com/topics/RowlandTodd.html">Rowland, Todd</a>. “Unitary Matrix.” From <a href="https://mathworld.wolfram.com/"><em>MathWorld</em></a> — A Wolfram Web Resource, created by <a href="https://mathworld.wolfram.com/about/author.html">Eric W. Weisstein</a>. <a href="https://mathworld.wolfram.com/UnitaryMatrix.html">https://mathworld.wolfram.com/UnitaryMatrix.html</a></p><p>[6] <a href="https://mathworld.wolfram.com/about/author.html">Weisstein, Eric W.</a> “Identity Matrix.” From <a href="https://mathworld.wolfram.com/"><em>MathWorld</em></a> — A Wolfram Web Resource. <a href="https://mathworld.wolfram.com/IdentityMatrix.html">https://mathworld.wolfram.com/IdentityMatrix.html</a></p><p>[7] IDENTITY Matrix. In: Wikipédia: a enciclopédia livre. Disponível em: &lt;<a href="https://en.wikipedia.org/wiki/Identity_matrix">https://pt.wikipedia.org/wiki/Conte%C3%BAdo_aberto</a>&gt; Acesso em: 26 nov 2020.</p><p>[8] Sakurai, J., Napolitano, J., &amp; Dahmen, S. (2013). <em>Mecânica quântica moderna</em>. Bookman.</p><p>[10] Horn, Roger A.; Johnson, Charles R. (1985). <em>Matrix Analysis</em>. [S.l.]: Cambridge University Press. <a href="https://pt.wikipedia.org/wiki/International_Standard_Book_Number">ISBN</a> <a href="https://pt.wikipedia.org/wiki/Especial:Fontes_de_livros/0-521-38632-2">0–521–38632–2</a></p><p>[11] Stulpe W. (2009) Self-Adjoint Operator. In: Greenberger D., Hentschel K., Weinert F. (eds) Compendium of Quantum Physics. Springer, Berlin, Heidelberg. <a href="https://doi.org/10.1007/978-3-540-70626-7_196">https://doi.org/10.1007/978-3-540-70626-7_196</a></p><p>[12] OPERADOR autoadjunto. In: Wikipédia: a enciclopédia livre. Disponível em: &lt;<a href="https://pt.wikipedia.org/wiki/Operador_autoadjunto">https://pt.wikipedia.org/wiki/Operador_autoadjunto</a>&gt; Acesso em: 26 nov 2020.</p><p>[13] Nielsen, M., &amp; Chuang, I. (2010). <em>Quantum Computation and Quantum Information: 10th Anniversary Edition</em>. Cambridge: Cambridge University Press. doi:10.1017/CBO9780511976667</p><p>[14] Voorhoede, D., 2021. <em>S Gate</em>. [online] Quantum Inspire. Available at: &lt;https://www.quantum-inspire.com/kbase/s-gate/&gt; [Accessed 6 February 2021].</p><p>[15] Voorhoede, D., 2021. <em>T Gate</em>. [online] Quantum Inspire. Available at: &lt;https://www.quantum-inspire.com/kbase/t-gate/&gt; [Accessed 6 February 2021].</p><p>[16] Colin Wilmott. (2011). A generalized quantum SWAP gate. &lt;<a href="https://arxiv.org/abs/0811.1684">https://arxiv.org/abs/0811.1684</a>&gt; [Accessed 6 February 2021].</p><p>[17] Voorhoede, D., 2021. <em>Toffoli Gate</em>. [online] Quantum Inspire. Available at: &lt;https://www.quantum-inspire.com/kbase/toffoli/&gt; [Accessed 7 February 2021].</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ed014c43a381" width="1" height="1" alt=""><hr><p><a href="https://medium.com/cq-em-portugu%C3%AAs/portas-l%C3%B3gicas-qu%C3%A2nticas-ed014c43a381">Portas Lógicas Quânticas</a> was originally published in <a href="https://medium.com/cq-em-portugu%C3%AAs">CQ em Português</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Qubits]]></title>
            <link>https://medium.com/cq-em-portugu%C3%AAs/do-bit-ao-qubit-113975dca0f9?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/113975dca0f9</guid>
            <category><![CDATA[computação-quântica]]></category>
            <category><![CDATA[qubit]]></category>
            <category><![CDATA[informação-quântica]]></category>
            <category><![CDATA[computação]]></category>
            <category><![CDATA[tecnologia]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Sun, 19 Jul 2020 07:46:15 GMT</pubDate>
            <atom:updated>2023-02-03T07:37:30.689Z</atom:updated>
            <content:encoded><![CDATA[<h4>Os bits da computação quântica</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/629/1*iGFcOSW2ufodO_8neU3UjQ.png" /></figure><p>Os <em>q</em><strong><em>ubits</em></strong> são para a computação quântica o que os <em>b</em><strong><em>its</em></strong> são para a computação clássica.</p><p>É fundamental que se discorra, primeiramente, sobre a forma como as informações são concebidas de forma clássica nos computadores, com <em>bits</em>. Em seguida, uma explicação clara e objetiva sobre os <em>qubits</em> e as informações quânticas se torna mais “palatável”. É com essa premissa que esta pequena dissertação se desenvolve, visando transmitir ao leitor, aficionado pelo tema, algum conhecimento aplicável. Primeiro, uma seção sobre <em>bits</em>; em seguida, uma seção sobre <em>qubits</em>.</p><h3>Bits e informações “clássicas”</h3><p><strong><em>Bit</em></strong> (acrônimo de <em>Binary Term</em>) é a menor unidade de informação que existe em um computador clássico. O <em>bit</em> pode assumir, por vez, um de dois estados: o estado alto, denotado pelo algarismo “<strong>1”</strong> ou pela letra “<strong>H”</strong>, ou o estado baixo, denotado pelo algarismo “<strong>0”</strong> ou pela letra “<strong>L”</strong>. Estes dois estados têm interpretações físicas clássicas — podem representar tensões elétricas, correntes elétricas, cargas elétricas, entre outras coisas. A maneira pela qual o <em>bit</em> é armazenado, transmitido ou processado é o que define qual interpretação física é adequada.</p><h4>Combinações de bits</h4><p>A associação de múltiplos <em>bits</em> concebe as informações de mais de dois estados. Enquanto um <em>bit</em> tem um conjunto de dois estados (<strong>“{0,1}”</strong>), uma associação de dois <em>bits</em> tem um conjunto de quatro estados (<strong>“{00, 01, 10, 11}”</strong>), uma associação de três <em>bits</em> tem um conjunto de oito estados (<strong>“{000, 001, 010, 011, 100, 101, 110, 111}”</strong>), e, assim por diante, uma associação de <strong>“<em>n”</em></strong> <em>bits</em> tem um conjunto de <strong>2ⁿ</strong> estados.</p><p>Um artifício matemático que pode ser usado para representar estes conjuntos de estados de <strong>“<em>n”</em></strong> <em>bits</em> é o <strong>produto cartesiano </strong>(denotado pelo símbolo<strong> </strong>“×”)<strong>.</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/391/1*JKShkl1Ke2L6Q5MOKmcglw.png" /><figcaption>(1) Definição do produto cartesiano para um par de conjuntos A B</figcaption></figure><p>O produto cartesiano é um operador que produz um conjunto de tuplas com todas as combinações possíveis de elementos pertencentes aos conjuntos operandos.</p><p>O produto cartesiano pode ser usado com <em>bits</em> da seguinte forma:</p><p>Estados de 2 <em>bits</em>: <strong>{0,1}×{0,1} = {(0,0), (0,1), (1,0), (1,1)}</strong></p><p>Estados de 3 <em>bits</em>:<strong> {0,1}×{0,1}×{0,1} ={(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)}</strong></p><p>Estados de <strong><em>n</em></strong> <em>bits</em>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/542/1*Ivtbqp9bPWhkM9fngDmd2A.png" /><figcaption>(2) Produto cartesiano de <strong>n</strong> conjuntos <strong>{0,1}</strong></figcaption></figure><p>Talvez esta ultima definição não tenha ficado muito clara. Este símbolo “<strong>Π</strong>” (a letra grega Pi maiúscula) com a expressão “<strong>t=1</strong>” subscrita e a letra <strong><em>n</em></strong> sobrescrita é um <strong>produtório </strong>— uma sequência de produtos de <strong>n</strong> conjuntos <strong>{0,1}</strong>, tal como “<strong>{0,1}₁×{0,1}₂×…×{0,1}ₙ</strong>” . O resultado é um conjunto de <strong>2ⁿ</strong> diferentes tuplas “<strong>(x₁, x₂,…,xₙ)”</strong> das quais cada <strong>“xₜ”</strong> é um número <strong>0</strong> ou <strong>1</strong>.</p><h4>Números naturais como bits</h4><p>Todo sistema numérico tem uma base. O sistema numérico <strong>decimal</strong>, que é o sistema com o qual estamos mais acostumados, possui base <strong>10</strong> — os números naturais são representados por sequências de algarismos de 0 a 9 (10 símbolos diferentes). O número 152, por exemplo, é representado no sistema decimal pela sequência de algarismos “<strong>(1,5,2)</strong>”. Em um caso geral, um número natural <strong>“X”</strong> é representado no sistema decimal pela sequência de <strong>“n”</strong> algarismos “<strong>(x₍ₙ₋₁₎,…,x₂,x₁,x₀)</strong>”, tal que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/170/1*ukHgiCd743L9w9An_rPvMQ.png" /><figcaption>(3) Valor do número natural <strong>X</strong> no sistema decimal com <strong>n</strong> algarismos <strong>(…,x₂,x₁,x₀)</strong></figcaption></figure><p>O número <strong>152</strong>, por exemplo, equivale a <strong>1×10²+5×10¹+2×10⁰</strong>.</p><p>Da mesma forma, é possível formar números naturais com sequências de <em>bits</em> — basta usar o sistema numérico <strong>binário</strong>, de base <strong>2</strong>. No sistema binário, os números naturais são representados por sequências de algarismos de 0 a 1 (<em>bits</em>). Um número natural <strong>“X”</strong> é representado no sistema binário pela sequência de <strong>“n”</strong> <em>bits</em> “<strong>(x₍ₙ₋₁₎,…,x₂,x₁,x₀)</strong>”, tal que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/157/1*Dba7TL2GCpwvJigT1--LNQ.png" /><figcaption>(4) Valor do número natural <strong>X</strong> no sistema binário com <strong>n </strong>bits <strong>(…,x₂,x₁,x₀)</strong></figcaption></figure><p>Neste caso, como uma associação de <strong>“n”</strong> <em>bits</em> tem um conjunto de <strong>2ⁿ </strong>estados distintos, <strong>“X”</strong> só pode assumir valores de <strong>0</strong> até <strong>2ⁿ-1</strong>, o que corresponde a um total de <strong>2ⁿ </strong>valores diferentes (lembre-se que o “<strong>0</strong>” conta). Em termos matemáticos, isto significa que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/226/1*EOH_mpNsjdvyt46Nm9F51g.png" /><figcaption>(5) O conjunto dos valores de <strong>X</strong> com <strong>n</strong> bits</figcaption></figure><p>As tabelas a seguir mostram alguns exemplos de números naturais no sistema decimal e no sistema binário.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1R7hTZKNQ92iOnnw-rjqIQ.png" /></figure><p>Também é possível representar números inteiros, números reais e números complexos com sequências de <em>bits</em>, mas não convém explicar isso aqui.</p><h3>Qubits e informações quânticas</h3><p><strong>Qubit</strong> (acrônimo de <em>Quantum Bit</em>) é o equivalente do <em>bit</em> para a computação quântica. Assim como o <em>bit</em> é a menor unidade de informação da computação clássica, o <em>qubit</em> é a menor unidade de informação da computação quântica. Em contraste com os <em>bits</em>, um <em>qubit</em> pode assumir uma infinidade de estados, o que inclui os estados <strong>|0⟩</strong>, <strong>|1⟩</strong>, e superposições desses dois. No entanto, quando o estado do <em>qubit</em> é verificado experimentalmente, ele se manifesta probabilisticamente como <strong>|0⟩</strong> ou <strong>|1⟩</strong>. Esses infinitos estados do <em>qubit</em> são interpretados fisicamente como estados quânticos — estados de sistemas físicos que obedecem às leis da mecânica quântica.</p><h4>Estados do qubit</h4><p>Os estados de um <em>qubit</em> são definidos como vetores em espaços vetoriais complexos. O espaço de estados de um <em>qubit</em> possui uma base de dois vetores ortonormais: <strong>|0⟩</strong> e <strong>|1⟩</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/430/1*Ms2gfOKs2qyIt9PE5Yz3Rg.png" /><figcaption>(6) Vetores da base computacional do espaço de estados de um qubit</figcaption></figure><p>Como você deve ter reparado, um valor (como <strong>0</strong> ou <strong>1</strong>) entre os caracteres “<strong>|” </strong>e <strong>“⟩</strong>” corresponde a um vetor. Este símbolo é chamado <strong>ket</strong>. Também existe o símbolo <strong>bra</strong> (“<strong>⟨…|”</strong>), para o qual <strong>⟨x|</strong> corresponde à transposta conjugada do ket <strong>|x⟩</strong>. Neste caso, <strong>⟨x|y⟩</strong> é o produto interno dos vetores <strong>|x⟩ </strong>e <strong>|y⟩</strong>. Esta notação é chamada <strong>Bra-ket</strong> ou <strong>notação de Dirac</strong>. Os vetores que são representados pela notação <strong>Bra-ket</strong> pertencem a <strong>espaços de Hilbert</strong> — espaços vetoriais com noções de ângulo e distância que não necessariamente têm dimensões finitas.</p><p>Os estados de um <em>qubit</em> podem ser definidos pela seguinte combinação linear:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/221/1*NyLIUkVuDtagf5rj-hJfNg.png" /><figcaption>(7) Combinação linear do estado de um qubit</figcaption></figure><p>Onde <strong>|ψ⟩</strong> é um vetor no espaço vetorial ℂ² que representa o estado do <em>qubit, </em>e os coeficientes <strong>a₀</strong> e <strong>a₁</strong> são números complexos que representam as <strong>amplitudes de probabilidade</strong> dos estados <strong>|0⟩ </strong>e <strong>|1⟩</strong>.</p><p>Quando o estado <strong>|ψ⟩</strong> é medido experimentalmente, mesmo quando está em uma superposição dos estados <strong>|0⟩</strong> e <strong>|1⟩</strong>, sempre se manifesta probabilisticamente como <strong>|0⟩</strong> ou <strong>|1⟩</strong>. A probabilidade do estado <strong>|0⟩</strong> se manifestar é ‖<strong>a₀</strong>‖<strong>² </strong>(quadrado do absoluto de <strong>a₀</strong>), e a probabilidade do estado <strong>|1⟩</strong> se manifestar é ‖<strong>a₁</strong>‖<strong>² </strong>(quadrado do absoluto de <strong>a₁</strong>). A soma das probabilidades deve ser sempre 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/214/1*opKzbErqKd5iREJJ4YuBCA.png" /><figcaption>(8) Soma das probabilidades de um qubit</figcaption></figure><p>O fenômeno da “manifestação” probabilística dos estados do sistema quântico é conhecido como <strong>colapso do estado quântico</strong>.</p><h4>Identidade de Euler</h4><p>A expressão “<strong>e</strong>ⁱᶲ” (“<strong>e</strong>” elevado a “<strong>i</strong>” “<strong>phi</strong>”) é muito recorrente na computação quântica. A letra <strong>“e”</strong> é a constante de Euler, que vale aproximadamente <strong>2,718281828459045235360287</strong>. A letra “<strong>i</strong>” é a unidade imaginária (raiz quadrada de <strong>-1</strong>), e a letra grega “<strong>ϕ” </strong>(phi) é um ângulo qualquer em radianos. Esta expressão tem a seguinte definição:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/232/1*nvxaR-vYPvZD25P3ZJJKwQ.png" /><figcaption>(9)</figcaption></figure><p>Ou seja: “<strong>e</strong>ⁱᶲ” corresponde a um número complexo cuja parte real é “<strong>cosϕ” </strong>(cosseno de phi) e a parte imaginária é “<strong>sinϕ”</strong> (seno de phi).</p><p>Agora, considere as seguintes fórmulas:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/262/1*pmwHg5yzUIQvdSDKeED1SQ.png" /><figcaption>(10)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/395/1*ixt_x7u05NBbIiNEx8iHBg.png" /><figcaption>(11) Módulo de um número complexo <strong>z=x+iy</strong>, onde <strong>x</strong> e <strong>y</strong> são números reais</figcaption></figure><p>As fórmulas <strong>9</strong>, <strong>10</strong> e <strong>11</strong> juntas levam à seguinte conclusão:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/462/1*5NyLf7aOeWCQRy4R_IpAAg.png" /><figcaption>(12) Módulo de “<strong>e^(iϕ)</strong>”</figcaption></figure><p>Isto significa que, para qualquer valor de <strong>ϕ</strong>,<strong> </strong>“<strong>e</strong>ⁱᶲ” sempre corresponde a um número complexo de módulo <strong>1</strong>. Então, sempre que você, leitor, ver a expressão “<strong>e</strong>ⁱᶲ” em uma fórmula matemática, lembre-se, é um número complexo de módulo <strong>1</strong>.</p><p>Vale notar que, para um número real <strong>“u” </strong>qualquer, o módulo de “<strong>ue</strong>ⁱᶲ” equivale ao próprio <strong>“u”</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/333/1*mFjJ4s34BYnQDd1U-l81fg.png" /><figcaption>(14)</figcaption></figure><h4>Esfera de Bloch</h4><p>Representar graficamente um vetor em ℂ² não é tão simples. Um único número complexo com parte imaginária diferente de zero é análogo a um vetor em ℝ² (uma dimensão para a parte real e outra para a parte imaginária), e seguindo esta mesma lógica, um vetor em ℂ² é análogo a um vetor em ℝ⁴, que não pode ser representado graficamente usando o sistema de coordenadas cartesiano. No entanto, um vetor em ℂ² que representa especificamente o estado de um <em>qubit</em> pode ser generalizado pela seguinte fórmula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/1*e0bjSydzz3wXB3iX_QIT4Q.png" /><figcaption>(15)</figcaption></figure><p>Onde <strong>θ</strong> e <strong>ϕ</strong> são ângulos em radianos.</p><p>Usando esta fórmula (15), é possível representar graficamente o estado de um <em>qubit</em> em coordenadas polares, como mostra a imagem a seguir:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/423/1*EgNCe3Ja-cdIlnkGR1qE_A.png" /><figcaption>Esfera de Bloch. Fonte: <a href="https://pt.m.wikipedia.org/wiki/Ficheiro:Bloch_Sphere.svg">https://pt.m.wikipedia.org/wiki/Ficheiro:Bloch_Sphere.svg</a></figcaption></figure><p>Esta representação gráfica do estado de um <em>qubit</em> é denominada <strong>esfera de Bloch</strong>.</p><p>Repare que, na esfera de Bloch, <strong>θ</strong> é representado como o ângulo entre o vetor <strong>|ψ⟩</strong> e o eixo <strong>z</strong>, e <strong>ϕ</strong> é representado como o ângulo entre a projeção do vetor <strong>|ψ⟩</strong> no plano <strong>xy</strong> e o eixo <strong>x</strong>.</p><h4>Os estados |+〉, |-〉, |+i〉 e |-i〉</h4><p>Além das bases ortonormais <strong>|0⟩</strong> e <strong>|1⟩</strong>, existem mais estados notáveis para um <em>qubit</em>: <strong>|+⟩</strong>, <strong>|-⟩</strong>, <strong>|+i⟩</strong> e <strong>|-i⟩</strong> são estados de superposição notáveis por serem colineares ao eixo <strong>x</strong> ou ao eixo <strong>y</strong> na esfera de Bloch.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/404/1*zvOjMs69AUSGNLIJGeXHvw.jpeg" /><figcaption>Os 6 estados da esfera de Bloch. Fonte: <a href="https://commons.wikimedia.org/wiki/File:Six_states_Bloch_sphere.jpg">https://pt.m.wikipedia.org/wiki/Ficheiro:Bloch_Sphere.svg</a></figcaption></figure><p>Os estados <strong>|+⟩</strong> e <strong>|-⟩</strong> são alinhados com o eixo <strong>x</strong> na esfera de Bloch, e têm as seguintes definições:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/257/1*wowNsRGuMRGc28wA9V_rVg.png" /><figcaption>(16)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/257/1*9ShAHqIqMUnScumbg2gqdw.png" /><figcaption>(17)</figcaption></figure><p>Os estados <strong>|+i⟩</strong> e <strong>|-i⟩</strong> são alinhados com o eixo <strong>y</strong> na esfera de Bloch, e têm as seguintes definições:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/267/1*kpgJPNkbyNPwfgpPMiC5NA.png" /><figcaption>(18)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/267/1*5FYM4yEGoaKx71cUunFi-w.png" /><figcaption>(19)</figcaption></figure><p><strong>|+⟩</strong>, <strong>|-⟩</strong>, <strong>|+i⟩</strong> e <strong>|-i⟩</strong> são estados diferentes que têm as mesmas estatísticas de medição.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/508/1*6rE4WzAiXW2PsEHOxTfX-Q.png" /><figcaption>(20)</figcaption></figure><p>Qualquer um desses quatro estados, quando é submetido a uma medição, tende a colapsar como <strong>|0⟩</strong> ou <strong>|1⟩</strong> com probabilidades iguais a <strong>1/2</strong>. Ou seja, é aleatório. Além desses quatro estados, existe mais uma infinidade de estados que também têm essa mesma distribuição de probabilidade.</p><h4>Fase</h4><p>Suponha que, em uma situação hipotética, um estado quântico <strong>|ψ⟩</strong> definido como “<strong>|ψ⟩=a₀|0⟩+a₁|1⟩”</strong> é medido muitas (quase “infinitas”) vezes. <strong>25%</strong> das medições resultam em <strong>|0⟩</strong> e <strong>75%</strong> das medições resultam em <strong>|1⟩</strong>. Isso significa que as probabilidades ‖<strong>a₀</strong>‖<strong>² </strong>e ‖<strong>a₁</strong>‖<strong>²</strong> valem, respectivamente, <strong>1/4</strong> e <strong>3/4</strong>. Aí vai uma pergunta: é possível deduzir os valores das amplitudes <strong>a₀</strong> e <strong>a₁</strong> apenas calculando as raízes quadradas das probabilidades ‖<strong>a₀</strong>‖<strong>² </strong>e ‖<strong>a₁</strong>‖<strong>² </strong>?</p><p>A resposta é: <strong>não</strong>, pois <strong>a₀</strong> e <strong>a₁</strong> são números complexos. Existem infinitos números complexos “<strong>aₙ</strong>” com o mesmo módulo ‖<strong>aₙ</strong>‖.</p><p>Lembre-se de que todos os números complexos “<strong>ue</strong>ⁱᶲ” têm módulo <strong>“u”</strong> (veja na equação 14). Partindo desse pressuposto, é possível dizer que, se a probabilidade ‖<strong>a₁</strong>‖<strong>²</strong> é <strong>3/4</strong>, então a amplitude<strong> a₁</strong> é “<strong>(√3/√4)e</strong>ⁱᶲ” para algum valor desconhecido de <strong>ϕ</strong>. É aí que entra o conceito de <strong>fase</strong>: a fase é um parâmetro do estado quântico que não afeta as estatísticas de medição.</p><p>Veja novamente a equação 15:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/410/1*e0bjSydzz3wXB3iX_QIT4Q.png" /></figure><p>Repare que, dos dois parâmetros <strong>θ</strong> e <strong>ϕ</strong>, apenas o parâmetro <strong>θ</strong> afeta as estatísticas de medição de <strong>|ψ⟩</strong>. Para qualquer valor de <strong>ϕ</strong>, a distribuição de probabilidade da medição de <strong>|ψ⟩</strong> será a mesma<strong>. </strong>É dito que<strong> </strong>“<strong>e</strong>ⁱᶲ” é o fator de fase de <strong>|1⟩</strong> na combinação linear do estado <strong>|ψ⟩</strong>.</p><p>Os estados <strong>|+⟩</strong>, <strong>|-⟩</strong>, <strong>|+i⟩</strong> e <strong>|-i⟩</strong>, por exemplo, são estados cujos parâmetros <strong>ϕ </strong>são, respectivamente, “<strong>ϕ=0”</strong>, “<strong>ϕ=π”, “ϕ=π/2”</strong> e <strong>“ϕ=3π/2”.</strong> Nos quatro casos, “<strong>θ=π/4”.</strong></p><blockquote>‘Phase’ is a commonly used term in quantum mechanics, with several different meanings dependent upon context. At this point it is convenient to review a couple of these meanings. Consider, for example, the state “<strong><em>e</em></strong><em>ⁱᶿ</em><strong><em>|ψ⟩</em></strong><em>”</em>, where <strong><em>|ψ⟩ </em></strong>is a state vector, and θ is a real number. We say that the state “<strong><em>e</em></strong><em>ⁱᶿ</em><strong><em>|ψ⟩</em></strong><em>”</em> is equal to <strong><em>|ψ⟩</em></strong>, up to the global phase factor “<strong><em>e</em></strong><em>ⁱᶿ”</em>. It is interesting to note that the statistics of measurement predicted for these two states are the same.</blockquote><p>Esta citação é da obra <strong><em>Quantum Computation and Quantum Information</em></strong>, de <strong><em>Michel A. Nielsen</em></strong> e <strong><em>Isaac L. Chuang</em></strong>.</p><p>Em um estado “<strong>e</strong>ⁱᶿ<strong>|ψ⟩</strong>” de um <em>qubit</em> ou um registrador, o fator global de fase “<strong>e</strong>ⁱᶿ” não faz diferença no contexto de um algoritmo quântico, podendo inclusive ser desconsiderado. No entanto, a diferença entre as fases “<strong>e</strong>ⁱᶿ” e “<strong>e</strong>ⁱ⁽ᶿ⁺ᶲ⁾” em “<strong>e</strong>ⁱᶿ<strong>|ψ⟩ = αe</strong>ⁱᶿ<strong>|0⟩ + βe</strong>ⁱ⁽ᶿ⁺ᶲ⁾<strong>|1⟩”</strong> deve ser considerada, e inclusive é fundamental para o funcionamento de alguns algoritmos quânticos (como o algoritmo de Grover e a transformada de Fourier quântica).</p><h4>Registradores quânticos</h4><p>Um <strong>registrador quântico</strong> é um agrupamento de múltiplos <em>qubits</em>.</p><p>Todos os estados quânticos devem ser representados por vetores, inclusive estados formados por mais de um <em>qubit.</em> Neste caso, o produto cartesiano não serve. É necessário usar um operador que produza um terceiro vetor ao invés de um conjunto de tuplas para representar as combinações de estados dos <em>qubits</em>. Este operador é o <strong>produto tensorial</strong> (mais específicamente, produto de Kronecker), representado pelo símbolo “⊗”.</p><p>O estado que engloba um par de estados <strong>|a⟩</strong> e <strong>|b⟩ </strong>pode ser expresso como um produto tensorial de <strong>|a⟩</strong> e <strong>|b⟩ </strong>da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/180/1*t34QaQDupLUV-G6RumAIFA.png" /><figcaption>(21)</figcaption></figure><p>É dito que <strong>|ab⟩</strong> é o <strong>estado global</strong> do registrador constituído pelo par de <em>qubits</em> de estados <strong>|a⟩</strong> e <strong>|b⟩</strong>.</p><p>Este produto tensorial pode ser “aberto” da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/398/1*w530McvfV2eFCs1yy0xZ_A.png" /><figcaption>(22)</figcaption></figure><p>Onde “<strong>[a₀, a₁]</strong>ᵀ<strong>=|a⟩</strong>”<strong> </strong>e “<strong>[b₀, b₁]</strong>ᵀ<strong>=|b⟩</strong>”.</p><p>No geral, um produto tensorial entre um par de matrizes <strong>A </strong>e <strong>B </strong>tem a seguinte definição:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/1*ZzQTKZ37HsDluRIkRjnbig.png" /><figcaption>(23)</figcaption></figure><p>Voltando ao exemplo do par de <em>qubits</em>, suponha que os estados <strong>|a⟩</strong> e <strong>|b⟩</strong> são:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/245/1*1z1lL8MAUsCmnHPmPtOKPw.png" /><figcaption>(24)</figcaption></figure><p>O estado global <strong>|ab⟩</strong> pode ser definido como a seguinte combinação linear de 4 bases:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*0mLJYT4gz9Vkwem6cfYxXw.png" /><figcaption>(25)</figcaption></figure><p>Considerando <strong>|ψ⟩=|ab⟩</strong>,<strong> α=α₀β₀</strong>, <strong>β=α₀β₁</strong>, <strong>γ=α₁β₀</strong>, <strong>δ=α₁β₁</strong>, substituindo as amplitudes <strong>αₙβₘ</strong> pelas equivalentes <strong>α</strong>, <strong>β</strong>, <strong>γ</strong> e <strong>δ</strong>, temos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*oEFpkQcLAG_puQOmcKBqFg.png" /><figcaption>(26)</figcaption></figure><p>A soma das probabilidades deve ser igual a <strong>1</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/355/1*Ucj07xe0J-5DepemEmwl2w.png" /><figcaption>(27)</figcaption></figure><p>Partindo do pressuposto de que <strong>(α₀β₀)(α₁β₁)=(α₀β₁)(α₁β₀)</strong>, é possível afirmar que, para que a combinação linear de <strong>|ψ⟩</strong> seja de fato um produto tensorial das combinações lineares de <strong>|a⟩</strong> e <strong>|b⟩</strong>, a seguinte relação deve ser satisfeita:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/113/1*9yJEszitK9cyOiE14dKdNA.png" /><figcaption>(28)</figcaption></figure><p>Caso o estado global de um par de <em>qubits</em> não satisfaça esta relação, este estado global não pode ser representado como um produto tensorial de um par de combinações lineares independentes. Casos em que isto acontece serão explicados na seção sobre <em>qubits</em><strong> emaranhados</strong>.</p><h4>Qubits emaranhados</h4><p>Suponha que um registrador quântico de 2 <em>qubits</em> tem o seguinte estado global:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/258/1*o4d3xA4HMknKBQtP3xxB0g.png" /><figcaption>(29)</figcaption></figure><p>Este é um <strong>estado <em>bell</em></strong>, um estado de dois <em>qubits</em> emaranhados.</p><p>Representando o <strong>estado <em>bell</em></strong> no mesmo formato da equação 26, onde as amplitudes de probabilidade são <strong>α</strong>, <strong>β</strong>, <strong>γ</strong> e <strong>δ</strong>, temos que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/422/1*Gk6sqDwnRyZqS1l_-3xFBQ.png" /><figcaption>(30)</figcaption></figure><p>Neste caso, é evidente que a relação <strong>αδ=βγ</strong>, que equivale a <strong>½=0</strong>, é falsa (ou seja, <strong>αδ≠βγ</strong>). Isto significa que o estado <em>bell</em> não é um produto tensorial de duas combinações lineares independentes, e é isso o que define um emaranhamento na computação quântica — se um estado global de <strong>n</strong> <em>qubits</em> não pode ser representado como um “produtório tensorial” de <strong>n</strong> combinações lineares independentes, então há um emaranhamento no registrador.</p><p>Além desse primeiro, existem outros três <strong>estados <em>bell</em></strong>, também conhecidos como <strong>pares EPR</strong>. O conjunto dos quatro estados <em>bell</em> é o seguinte:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/1*WjdMc0ll1ubR6rjWAvMmOw.png" /><figcaption>(31) Os quatro estados bell</figcaption></figure><p>Os estados <em>bell</em> têm uma característica muito interessante: em uma situação ideal, quando o estado do registrador é medido e um dos <em>qubits</em> colapsa em <strong>|0⟩</strong> ou <strong>|1⟩</strong>, é possível inferir como o outro <em>qubit</em> colapsou. Por exemplo: nos estados <strong>|β₀₀⟩</strong> e <strong>|β₀₁⟩</strong>, quando um dos <em>qubits</em> colapsa em <strong>|0⟩</strong>, o outro necessariamente colapsa em <strong>|0⟩</strong>. Da mesma forma, quando um dos <em>qubits</em> colapsa em <strong>|1⟩</strong>, o outro necessariamente também colapsa em <strong>|1⟩</strong>.</p><blockquote>If we can represent an n-qubit state as the tensor product of the states of individual Qubits “<strong><em>|q₀,q₁,…,qₙ⟩=|q₀⟩⊗|q₁⟩⊗…⊗|qₙ⟩</em>”</strong>, the state is called separable. However, due to the nature of superposition, it may be that a<br>multi-qubit state is non-separable and individual qubit states are not well defined independent of other qubits. This non-local correlation phenomenon known as <strong>entanglement</strong> is a necessary resource to achieve the exponential speedup of quantum compared to classic computation.</blockquote><p>Esta citação é da obra <strong><em>Mastering Quantum Computing with IBM QX</em></strong>, da <strong><em>Dra. Christine Corbett Moran</em></strong>.</p><h3>Referências bibliográficas</h3><ul><li>Livro <strong>Quantum Computing and Quantum Information</strong>, dos autores <strong>Michael A. Nielsen</strong> e <strong>Isaac L. Chuang</strong>. Editora <strong>Cambridge University Press</strong>. <a href="https://doi.org/10.1017/CBO9780511976667">https://doi.org/10.1017/CBO9780511976667</a></li><li>Livro <strong>Mastering Quantum Computing with IBM QX</strong>, da autora <strong>Dr. Christine Corbett Moran</strong>. Editora<strong> Packt</strong>. ISBN 9781789136432. Informações disponíveis em <a href="https://www.packtpub.com/application-development/mastering-quantum-computing-ibm-qx">https://www.packtpub.com/application-development/mastering-quantum-computing-ibm-qx</a> (acesso em 27 jun 2020)</li><li>Livro <strong>Quantum Computing for Computer Scientists</strong>, dos autores <strong>Noson f. Yanofsky</strong> e <strong>Mirco A. Mannucci</strong>. <a href="https://doi.org/10.1017/CBO9780511813887">https://doi.org/10.1017/CBO9780511813887</a></li><li>Monografia <strong>Uma Introdução à Computação Quântica</strong>, dos autores <strong>André Luís Vignatti</strong>, <strong>Francisco Summa Netto</strong> e <strong>Luiz Fernando Bittencourt</strong>. Defendida no<strong> Departamento de Informática da Universidade do Paraná</strong>. Disponível em <a href="https://www.ic.unicamp.br/~bit/arquivos/tg.pdf">https://www.ic.unicamp.br/~bit/arquivos/tg.pdf</a> (acesso em 27 jun 2020)</li><li>Artigo <strong>Uma Introdução aos Algoritmos Quânticos</strong>, dos autores <strong>Renato Portugal </strong>(<strong>LNCC</strong>), <strong>Carlile C. Lavor</strong> (<strong>IME-UERJ</strong>), <strong>Luiz M. Carvalho</strong> (<strong>IME-UERJ</strong>) e <strong>Nelson Maculan </strong>(<strong>COPPE-UFRJ</strong>).</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=113975dca0f9" width="1" height="1" alt=""><hr><p><a href="https://medium.com/cq-em-portugu%C3%AAs/do-bit-ao-qubit-113975dca0f9">Qubits</a> was originally published in <a href="https://medium.com/cq-em-portugu%C3%AAs">CQ em Português</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Uma introdução à matemática da computação quântica]]></title>
            <link>https://medium.com/programadores-ajudando-programadores/uma-introdu%C3%A7%C3%A3o-%C3%A0-matem%C3%A1tica-da-computa%C3%A7%C3%A3o-qu%C3%A2ntica-22763e797b8d?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/22763e797b8d</guid>
            <category><![CDATA[computação-quântica]]></category>
            <category><![CDATA[ciência-da-computação]]></category>
            <category><![CDATA[informação-quântica]]></category>
            <category><![CDATA[computação]]></category>
            <category><![CDATA[matemática]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Sat, 27 Jun 2020 17:38:19 GMT</pubDate>
            <atom:updated>2022-06-18T07:00:45.243Z</atom:updated>
            <content:encoded><![CDATA[<p>Meu objetivo ao escrever este texto é apresentar uma abordagem objetiva e direta sobre a matemática da computação quântica. O conteúdo que será apresentado aqui não vai ser o suficiente para que o leitor termine a leitura capacitado a começar a desenvolver os próprios algoritmos quânticos e escrever artigos a respeito, mas será o bastante para dar uma breve noção introdutória sobre o tema.</p><p>Para a plena compreensão deste conteúdo, é importante que o leitor tenha algum conhecimento prévio de álgebra linear e ciência da computação.</p><p>Caso você, leitor, não faça nem ideia do que seja a computação quântica, eu sugiro que assista este vídeo antes de prosseguir com a leitura:</p><iframe src="https://cdn.embedly.com/widgets/media.html?src=https%3A%2F%2Fwww.youtube.com%2Fembed%2F92eSz2X0AlU%3Ffeature%3Doembed&amp;display_name=YouTube&amp;url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3D92eSz2X0AlU&amp;image=https%3A%2F%2Fi.ytimg.com%2Fvi%2F92eSz2X0AlU%2Fhqdefault.jpg&amp;key=a19fcc184b9711e1b4764040d3dc5c07&amp;type=text%2Fhtml&amp;schema=youtube" width="854" height="480" frameborder="0" scrolling="no"><a href="https://medium.com/media/f6110553a31adfc2c7542b2bd48caa43/href">https://medium.com/media/f6110553a31adfc2c7542b2bd48caa43/href</a></iframe><h4>Bits clássicos e bits quânticos</h4><p>Um <em>bit</em> (clássico) é um termo binário: basicamente, um valor numérico pertencente ao conjunto <strong>{0,1}</strong>. O valor do <em>bit</em> pode ter diversas interpretações físicas: pode ser uma tensão elétrica, uma corrente elétrica, uma carga, etc. A regra é: o <em>bit</em> clássico sempre valerá 0 ou 1, nunca 0 e 1 simultaneamente.</p><p>Os <em>qubits</em> (<em>bits</em> quânticos) são termos binários que podem assumir estados superpostos (a grosso modo, 1 e 0 ao mesmo tempo). Os estados desses <em>bits</em> quânticos devem ser representados como vetores.</p><p>Os <em>qubits</em> possuem duas bases ortonormais: <strong>|0⟩</strong> e <strong>|1⟩</strong>, onde:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/430/1*Ms2gfOKs2qyIt9PE5Yz3Rg.png" /><figcaption>(1)</figcaption></figure><p>Como você deve ter reparado, um valor (como <strong>0</strong> ou <strong>1</strong>) entre os caracteres “<strong>|” </strong>e <strong>“⟩</strong>” corresponde a um vetor. Este símbolo é chamado <strong>ket</strong>. Também existe o símbolo <strong>bra</strong> (“<strong>⟨…|”</strong>), para o qual <strong>⟨x|</strong> corresponde à transposta conjugada do ket <strong>|x⟩</strong>. Neste caso, <strong>⟨x|y⟩</strong> é o produto interno dos vetores <strong>|x⟩ </strong>e <strong>|y⟩</strong>. Esta notação é chamada <strong>Bra-ket</strong> ou <strong>notação de Dirac</strong>. Os vetores que são representados pela notação <strong>Bra-ket</strong> pertencem a <strong>espaços de Hilbert</strong> —<strong> </strong>espaços vetoriais com noções de ângulo e distância que não necessariamente têm dimensões finitas.</p><p>Os possíveis estados de um <em>qubit</em> podem ser expressos pela seguinte combinação linear:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/252/1*emgd8cNBA7yaFL0l1vq34g.png" /><figcaption>(2)</figcaption></figure><p>Onde <strong>|ψ⟩</strong> é um vetor no espaço vetorial ℂ² que representa o estado do <em>qubit, </em>e os coeficientes <strong>ω₀</strong> e <strong>ω₁</strong> são números complexos que representam as <strong>amplitudes de probabilidade</strong> dos estados <strong>|0⟩ </strong>e <strong>|1⟩</strong>.</p><p>Quando o estado <strong>|ψ⟩</strong> é medido experimentalmente, manifesta um dos estados base <strong>|0⟩ </strong>e <strong>|1⟩</strong> (fenômeno este que é conhecido na mecânica quântica como “colapso”). A probabilidade do estado <strong>|0⟩</strong> se manifestar é <strong>|ω₀|² </strong>(quadrado do absoluto de <strong>ω₀</strong>), e a probabilidade do estado <strong>|1⟩</strong> se manifestar é <strong>|ω₁|² </strong>(quadrado do absoluto de <strong>ω₁</strong>). Isto significa que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/234/1*c0C45juXE8aIIsHMnR63_A.png" /><figcaption>(3)</figcaption></figure><h4>Esfera de Bloch</h4><p>Representar graficamente um vetor em ℂ² não é tão simples. Um único número complexo com parte imaginária diferente de zero é análogo a um vetor em ℝ² (uma dimensão para a parte real e outra para o fator real da unidade imaginária), e seguindo esta mesma lógica, um vetor em ℂ² é análogo a um vetor em ℝ⁴, que não pode ser representado graficamente usando o sistema de coordenadas cartesiano. No entanto, um vetor em ℂ² que representa especificamente o estado de um <em>qubit</em> pode ser generalizado pela seguinte fórmula:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/347/1*x2eYfcKXA5tZP5jPncrrMg.png" /><figcaption>(4)</figcaption></figure><p>Onde <strong>θ</strong> e <strong>ϕ</strong> são ângulos em radianos.</p><p>Usando esta fórmula (4), é possível representar graficamente o estado de um <em>qubit</em> em coordenadas polares, como mostra a imagem a seguir:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/535/1*hdhe3_LOYJTnsl29n44Evg.png" /><figcaption>Esfera de Bloch. Fonte: <a href="https://www.researchgate.net/figure/Figura-A1-Esfera-de-Bloch-O-estado-ps-de-um-qubitequbite-representado-por-um-ponto_fig5_266440528">https://www.researchgate.net/figure/Figura-A1-Esfera-de-Bloch-O-estado-ps-de-um-qubitequbite-representado-por-um-ponto_fig5_266440528</a></figcaption></figure><p>Esta representação gráfica do estado de um <em>qubit</em> é denominada <strong>esfera de Bloch</strong>.</p><p>Repare que, na esfera de Bloch, <strong>θ</strong> é representado como o ângulo entre o vetor <strong>|ψ⟩</strong> e o eixo <strong>z</strong>, e <strong>ϕ</strong> é representado como o ângulo entre a projeção do vetor <strong>|ψ⟩</strong> no plano <strong>xy</strong> e o eixo <strong>x</strong>.</p><h4>Registradores quânticos e estados globais</h4><p>Com <strong><em>n</em></strong> <em>bits</em>, é possível formar <strong>2ⁿ</strong> combinações de <strong>1</strong> e <strong>0</strong>. Por exemplo: com um par de <em>bits</em> (um <em>crumb</em>) é possível formar as combinações <strong>00</strong>, <strong>01</strong>, <strong>10</strong> e <strong>11</strong> (um total de 2² combinações). Isso pode ser expresso matematicamente usando conjuntos, considerando <strong><em>bit={0,1}</em></strong>, da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/396/1*zo5iSAfpwjfpuVtIqWt7MA.png" /><figcaption>(5)</figcaption></figure><p>Este símbolo parecido com a letra “x” na equação 5 é um <strong>produto cartesiano </strong>—<strong> </strong>um operador que produz um conjunto de tuplas com todas as combinações possíveis de elementos pertencentes aos conjuntos operandos. Este operador tem a seguinte definição:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/411/1*4RTBU0pqXApREr3IqCjGTA.png" /><figcaption>(6)</figcaption></figure><p>Com <em>qubits</em> é diferente: todos os estados devem ser representados por vetores, inclusive estados formados por mais de um <em>qubit.</em> Neste caso, o produto cartesiano não serve. É necessário usar um operador que produza um terceiro vetor ao invés de um conjunto de tuplas para representar as combinações de estados dos <em>qubits</em>. Este operador é o <strong>produto tensorial</strong> (também conhecido como <em>kronecker</em>), representado pelo símbolo “⊗”.</p><p>O estado de um “<em>crumb</em> de <em>qubits</em>” de estados <strong>|a⟩</strong> e <strong>|b⟩ </strong>pode ser expresso como um produto tensorial de <strong>|a⟩</strong> e <strong>|b⟩ </strong>da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/180/1*t34QaQDupLUV-G6RumAIFA.png" /><figcaption>(7)</figcaption></figure><p>Onde <strong>|ab⟩</strong> é o <strong>estado global</strong> do par de <em>qubits</em>.</p><p>Este produto tensorial pode ser expresso mais detalhadamente da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/398/1*w530McvfV2eFCs1yy0xZ_A.png" /><figcaption>(8)</figcaption></figure><p>No geral, um produto tensorial entre um par de matrizes <strong>A </strong>e <strong>B </strong>tem a seguinte definição:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/533/1*ZzQTKZ37HsDluRIkRjnbig.png" /><figcaption>(9)</figcaption></figure><p>Voltando ao exemplo do <em>crumb —</em> definindo os <em>qubits</em> <strong>|a⟩</strong> e <strong>|b⟩</strong> como:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/245/1*1z1lL8MAUsCmnHPmPtOKPw.png" /><figcaption>(10)</figcaption></figure><p>O estado global <strong>|ab⟩</strong> pode ser definido como a seguinte combinação linear de 4 bases:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/576/1*0mLJYT4gz9Vkwem6cfYxXw.png" /><figcaption>(11)</figcaption></figure><p>Considerando <strong>|ψ⟩=|ab⟩</strong>,<strong> α=α₀β₀</strong>, <strong>β=α₀β₁</strong>, <strong>γ=α₁β₀</strong>, <strong>δ=α₁β₁</strong>, substituindo as amplitudes <strong>αₙβₘ</strong> pelas equivalentes <strong>α</strong>, <strong>β</strong>, <strong>γ</strong> e <strong>δ</strong>, temos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/409/1*oEFpkQcLAG_puQOmcKBqFg.png" /><figcaption>(12)</figcaption></figure><p>Onde:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/355/1*Ucj07xe0J-5DepemEmwl2w.png" /><figcaption>(13)</figcaption></figure><p>Partindo do pressuposto de que <strong>(α₀β₀)(α₁β₁)=(α₀β₁)(α₁β₀)</strong>, é possível afirmar que, para que a combinação linear de <strong>|ψ⟩</strong> (12) seja de fato um produto tensorial das combinações lineares de <strong>|a⟩</strong> e <strong>|b⟩</strong> (10), a seguinte relação deve ser satisfeita:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/113/1*9yJEszitK9cyOiE14dKdNA.png" /><figcaption>(14)</figcaption></figure><p>Caso o estado global de um par de <em>qubits</em> não satisfaça esta relação, este estado global não pode ser representado como um produto tensorial de um par de combinações lineares independentes. Casos em que isto acontece serão explicados na seção sobre <strong><em>qubits</em> emaranhados</strong>.</p><p>No geral, agrupamentos de múltiplos <em>qubits</em> usados por um algoritmo quântico são denominados <strong>registradores quânticos</strong>. Em contraste com os computadores clássicos, que normalmente só trabalham com agrupamentos de <strong>2ⁿ</strong> <em>bits —</em> normalmente 4 <em>bits</em> (<em>nyble</em>), 8 <em>bits</em> (<em>byte</em>), 16 <em>bits</em> (<em>word</em>), 32 <em>bits</em> (<em>long word</em>) e 64 <em>bits</em> (<em>very long word</em>) — os computadores quânticos não são projetados para trabalhar necessariamente com agrupamentos de <strong>2ⁿ</strong> <em>qubits</em>. Um exemplo disso é o computador quântico <strong>ibmqx4</strong>, da <strong>IBM</strong>, que trabalha com 5 <em>qubits</em>.</p><h4><em>Qubits</em> emaranhados</h4><p>Suponha que um registrador quântico de 2 <em>qubits</em> tem o seguinte estado global:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/258/1*o4d3xA4HMknKBQtP3xxB0g.png" /><figcaption>(15)</figcaption></figure><p>Este é um <strong>estado <em>bell</em></strong>, um estado de dois <em>qubits</em> emaranhados.</p><p>Representando o <strong>estado <em>bell</em></strong> no mesmo formato da equação 12, onde as amplitudes de probabilidade são <strong>α</strong>, <strong>β</strong>, <strong>γ</strong> e <strong>δ</strong>, temos que:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/422/1*Gk6sqDwnRyZqS1l_-3xFBQ.png" /><figcaption>(16)</figcaption></figure><p>Neste caso, é evidente que a relação <strong>αδ=βγ</strong>, que equivale a <strong>½=0</strong>, é falsa (ou seja, <strong>αδ≠βγ</strong>). Isto significa que o estado <em>bell</em> não é um produto tensorial de duas combinações lineares independentes, e é isso o que define um emaranhamento na computação quântica — se um estado global de <strong>n</strong> <em>qubits</em> não pode ser representado como um “produtório tensorial” de <strong>n</strong> combinações lineares independentes, então há um emaranhamento no registrador.</p><p>O emaranhamento quântico é fundamental para a computação quântica, pois com ele é possível estabelecer uma relação lógica entre os estados base que os <em>qubits</em> manifestam quando são submetidos a medições. No estado <em>bell</em>, por exemplo, em uma situação em que ambos os <em>qubits</em> do registrador são submetidos a uma medição: se o primeiro <em>qubit</em> manifesta o estado <strong>|1⟩</strong>, o segundo <em>qubit</em> necessariamente também manifesta estado <strong>|1⟩</strong>; se o primeiro <em>qubit</em> manifesta o estado <strong>|0⟩</strong>, o segundo <em>qubit</em> necessariamente também manifesta o estado <strong>|0⟩</strong>. Representando o estado <strong>|1⟩</strong> como <strong>V</strong>,<strong> </strong>o estado <strong>|0⟩</strong> como <strong>F</strong>, o estado que o primeiro <em>qubit</em> manifesta como <strong>q₀</strong> e o estado que o segundo <em>qubit</em> manifesta como <strong>q₁</strong>, podemos representar esta relação pela seguinte expressão lógica:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/102/1*YbqfaXf-Y5Dejd9JJMY2wQ.png" /><figcaption>(17)</figcaption></figure><p>Se fizermos o mesmo com o seguinte estado de dois <em>qubits</em> emaranhados:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/259/1*SEZtQ1NIhC6pOA86_67Z6A.png" /><figcaption>(18)</figcaption></figure><p>Temos a seguinte relação lógica:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/113/1*XR-PPeem8Gc0LoylwY3j7Q.png" /><figcaption>(19)</figcaption></figure><p>E se fizermos o mesmo com o seguinte estado de três <em>qubits</em>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/443/1*ro-woG8qttla2-IFPyGNzQ.png" /><figcaption>(20)</figcaption></figure><p>Temos a seguinte relação lógica:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/142/1*2dO0r1oQQYm5thOM6Rd5hA.png" /><figcaption>(21)</figcaption></figure><p>Utilizando emaranhamento quântico, é possível criar as mais diversas relações lógicas entre os estados que os <em>qubits</em> manifestam nas medições, possibilitando até que operações lógicas, relacionais e aritméticas sejam feitas com grandes quantidades de informações quânticas.</p><h4>Portas lógicas quânticas</h4><p>Na eletrônica digital, os circuitos são constituídos por portas lógicas <strong>NOT</strong>, <strong>AND</strong>, <strong>OR</strong>,<strong> XOR</strong>, e derivadas, que criam relações lógicas com os <em>bits</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-oHH8e8E_aDl0QHW9hPS6Q.png" /><figcaption>Portas lógicas digitais. Fonte: <a href="https://instrumentationtools.com/logic-gates/">https://instrumentationtools.com/logic-gates/</a></figcaption></figure><p>Já na computação quântica, existem as portas lógicas quânticas, que são matrizes unitárias responsáveis por modificar os estados dos <em>qubits</em>. Entre elas, podemos citar as portas <strong>Pauli-X</strong>, <strong>Pauli-Y</strong>, <strong>Pauli-Z</strong>, <strong>Hadamard</strong>, <strong>Phase</strong>, <strong>T</strong>, <strong>Controlled-NOT</strong>, entre outras. Além destas, existem portas compostas por combinações de outras portas (como as portas <strong>Toffoli, Swap</strong> e <strong>Controlled-Z</strong>), portas de rotação em ângulo livre na esfera de <em>Bloch</em> (<strong>Rx</strong>, <strong>Ry</strong> e <strong>Rz</strong>), e portas transpostas conjugadas (como as portas <strong>S†</strong> e <strong>T†</strong> ). A aplicação de uma porta lógica quântica se da, em termos matemáticos, por um produto matricial da matriz unitária da porta com o vetor de estado de um ou mais <em>qubits.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*SiHGFQcNIN_n4vKuYAnBwA.png" /><figcaption>Portas logicas quânticas (em inglês). Fonte: <a href="https://commons.wikimedia.org/wiki/File:Quantum_Logic_Gates.png">https://commons.wikimedia.org/wiki/File:Quantum_Logic_Gates.png</a></figcaption></figure><p>Portas como <strong>Pauli-X</strong>, <strong>Pauli-Y</strong>, <strong>Pauli-Z</strong>, <strong>Hadamard</strong>, <strong>Phase</strong>, <strong>T</strong>, <strong>Rx</strong>, <strong>Ry</strong> e <strong>Rz</strong> são portas de <em>qubit</em> único. Estas portas servem para rotacionar o vetor de estado do <em>qubit</em> na esfera de <em>Bloch</em> em determinado ângulo e eixo de rotação. Por exemplo: as portas <strong>Pauli-X, Pauli-Y</strong> e <strong>Pauli-Z</strong> induzem rotações de <strong>π</strong> radianos nos respectivos eixos <strong>x</strong>, <strong>y</strong> e <strong>z</strong> da esfera de <em>Bloch</em>, como mostra as animações a seguir (que foram retiradas da página <a href="https://quantum-computing.ibm.com/docs/circ-comp/q-gates">https://quantum-computing.ibm.com/docs/circ-comp/q-gat</a>es):</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*uKOTj3i8hQ1y-HLbZmmjzQ.gif" /><figcaption><strong>Rotação da porta Pauli-X. </strong>Fonte: <a href="https://quantum-computing.ibm.com/docs/circ-comp/q-gates">https://quantum-computing.ibm.com/docs/circ-comp/q-gates</a></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*ElD4v2qpO9dirOEcE_fXSQ.gif" /><figcaption><strong>Rotação da porta Pauli-Y. </strong>Fonte: <a href="https://quantum-computing.ibm.com/docs/circ-comp/q-gates">https://quantum-computing.ibm.com/docs/circ-comp/q-gates</a></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*NFQJLM8gA0mNuVNpoTRFOw.gif" /><figcaption><strong>Rotação da porta Pauli-Z. </strong>Fonte: <a href="https://quantum-computing.ibm.com/docs/circ-comp/q-gates">https://quantum-computing.ibm.com/docs/circ-comp/q-gates</a></figcaption></figure><p>As portas <strong>Phase</strong> e <strong>T</strong> produzem rotações no eixo <strong>z</strong> com os respectivos ângulos <strong>π/2</strong> e <strong>π/4</strong>, como mostra as seguintes animações:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*EeR2BfpXbRBVP8u-rhIilQ.gif" /><figcaption><strong>Rotação da porta Phase. </strong>Fonte: <a href="https://quantum-computing.ibm.com/docs/circ-comp/q-gates">https://quantum-computing.ibm.com/docs/circ-comp/q-gates</a></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*qsngJ3Hd4tvTPtv4DeUpFg.gif" /><figcaption><strong>Rotação da porta T. </strong>Fonte: <a href="https://quantum-computing.ibm.com/docs/circ-comp/q-gates">https://quantum-computing.ibm.com/docs/circ-comp/q-gates</a></figcaption></figure><p>Portas como <strong>Controlled-NOT</strong>, <strong>Controlled-Z</strong> e <strong>Toffoli</strong> trabalham com mais de um <em>qubit.</em> Elas servem para criar ou desfazer um emaranhamento nos <em>qubits</em> operandos. A porta <strong>Controlled-NOT</strong> (que aqui será simbolizada por <strong>Cx</strong>), por exemplo, produz a seguinte relação lógica com os estados base dos <em>qubits</em> operandos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/203/1*uwGC3eTR-q6E2VNNIWW01Q.png" /><figcaption>(22)</figcaption></figure><p>Ou seja, ela cria uma relação lógica <strong>XOR</strong> (o operador booleano “⊕”) entre os dois <em>qubits</em> operandos<em>,</em> comportando-se como uma porta <strong>Pauli-X</strong> no <em>qubit</em> <strong><em>a</em></strong> quando o estado do <em>qubit </em><strong><em>b</em></strong> se manifesta como <strong>|1⟩</strong> na medição.</p><p>Já a porta <strong>Toffoli</strong> (que aqui será simbolizada por <strong>Ccx</strong>) produz a seguinte relação lógica com os estados base dos <em>qubits</em> operandos:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/468/1*Uf8fZTVYjbUTS9dHfNFiBg.png" /><figcaption>(23)</figcaption></figure><p>Ou seja, ela cria uma relação lógica <strong>XOR</strong> com <strong>AND</strong>,<strong> </strong>comportando-se como uma porta <strong>Pauli-X</strong> no <em>qubit</em> <strong><em>a</em></strong> quando o estado dos <em>qubits</em> <strong><em>b</em></strong> e <strong><em>c</em></strong> se manifesta como <strong>|11⟩</strong> na medição.</p><p>Eis a função principal das portas controladas (como <strong>Controlled-NOT</strong>, <strong>Controlled-Z</strong> e <strong>Toffoli</strong>): elas se comportam como uma rotação no estado de um <em>qubit</em> alvo quando o estado de um ou mais <em>qubits</em> de controle se manifestam como <strong>|1⟩</strong> na medição.</p><h4>Algoritmos quânticos</h4><p>Agora que você, leitor, já tem uma breve noção do que são portas lógicas quânticas, é hora de abordar o que provavelmente é a parte mais importante da computação quântica: os algoritmos quânticos.</p><p>Um algoritmo quântico é uma combinação de portas lógicas quânticas trabalhando sobre um registrador quântico com o objetivo de processar informações codificadas no estado global do registrador. Estas combinações de portas lógicas quânticas são programadas com o auxilio de computadores clássicos. As respostas do algoritmo quântico são obtidas pela medição dos estados dos <em>qubits</em>.</p><p>Uma combinação de portas lógicas é, matematicamente, uma série de produtos matriciais e produtos tensoriais entre matrizes unitárias. Por exemplo: um algoritmo quântico capaz de transformar o estado <strong>|00⟩</strong> em um estado <em>bell</em> pode ser descrito algebricamente pela seguinte equação:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/397/1*vYQe6T3OzHhy28itny_7Vw.png" /><figcaption>(24)</figcaption></figure><p>Onde <strong>Cx</strong> é a porta <strong>Controlled-NOT</strong>, <strong>H</strong> é a porta <strong>Hadamard</strong> e <strong>I₂</strong> é uma matriz identidade <strong>2x2</strong>. Esta mesma equação pode ser “aberta” da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/601/1*gWAlETJ9rK0MZG0kyW4_Gg.png" /><figcaption>(25)</figcaption></figure><p>É claro que equações não são uma forma muito intuitiva de representar algoritmos quânticos, principalmente quando há uma quantidade grande de <em>qubits</em> e portas lógicas quânticas no algoritmo. Uma representação mais intuitiva para os algoritmos quânticos são os <strong>circuitos quânticos</strong>, que são diagramas em que os <em>qubits</em> são representados por linhas horizontais e as portas lógicas quânticas são representadas por blocos, símbolos e linhas verticais, desenhados sobre as linhas horizontais dos <em>qubits</em>. A imagem a seguir mostra o circuito quântico correspondente ao algoritmo da equação 24:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/1*91aD1z83ltL4veB0qCZPGw.png" /><figcaption>Circuito quântico que produz o estado bell</figcaption></figure><p>Neste diagrama, um bloco com a letra “H” representa a porta <strong>Hadamard</strong> operando sobre o <em>qubit</em> <strong>q₀</strong>, e uma linha vertical com um ponto na extremidade superior e o simbolo “⊕” na extremidade inferior representa a porta <strong>Controlled-NOT</strong> operando sobre os <em>qubits</em> <strong>q₀</strong> (controle) e <strong>q₁</strong> (alvo). Os blocos com “reloginhos” representam as medições dos estados dos <em>qubits</em>.</p><p>Simulando 1024 medições sucessivas da saída deste circuito, o seguinte histograma é obtido:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/405/1*r1CzfrlufcJzgWAE_7daKA.png" /><figcaption>Histograma do resultado de 1024 medições do estado bell</figcaption></figure><p>Observe que as probabilidades calculadas experimentalmente têm um pequeno erro e não são exatamente iguais a 50%. Isto é normal. Quanto mais medições forem feitas, menos errático será este calculo experimental. Mas vale lembrar que este experimento foi feito em um simulador. Se estivéssemos trabalhando com um dos atuais computadores <strong>NISQ</strong> (<em>Noisy Intermediate-Scale Quantum</em>), ainda teríamos uma quantidade razoável de ruídos interferindo nos resultados finais do experimento (o que é péssimo).</p><p>Existem alguns algoritmos quânticos notáveis. O <strong>algoritmo de Shor</strong>, por exemplo, é um algoritmo quântico capaz de decompor números inteiros grandes em fatores primos de forma rápida, e pode ser usado para quebrar a segurança de sistemas de informação que usam criptografia <em>RSA</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ZHtc-4YQlkYXoE5wm74rKg.png" /><figcaption>Sub-rotina quântica do algoritmo de Shor. Fonte: <a href="https://commons.wikimedia.org/wiki/File:Shor%27s_algorithm.svg">https://commons.wikimedia.org/wiki/File:Shor%27s_algorithm.svg</a></figcaption></figure><p>Outro exemplo é o protocolo de comunicação <strong><em>superdense coding</em></strong>, que codifica a informação de um par de <em>bits</em> clássicos em um estado quântico de dois <em>qubits</em> para transmiti-la de um remetente para um destinatário com segurança.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/542/1*rLW-0KaedUAe6UIAqpRzEA.png" /><figcaption>Esquemático do circuito quântico usado no protocolo <strong>superdense coding</strong>. Fonte: <a href="https://commons.wikimedia.org/wiki/File:Superdense_coding.png">https://commons.wikimedia.org/wiki/File:Superdense_coding.png</a></figcaption></figure><p>Existem muitos algoritmos quânticos notáveis dos quais simplesmente não vale a pena abordar aqui. Caso o leitor tenha interesse em conhecê-los, sugiro que dê especial atenção ao <strong>algoritmo quântico de busca </strong>(também conhecido como <strong>algoritmo de Grover</strong>) e à <strong>transformada discreta quântica de Fourier</strong> (ou simplesmente <strong>QFT</strong>), que inclusive é a base do <strong>algoritmo de Shor</strong>. São dois algoritmos muito importantes para a computação quântica.</p><h4>Conclusão</h4><p>Ainda que objetiva, esta foi uma abordagem muito breve e superficial, cujo intuito foi apenas dar uma pequena noção ao leitor sobre a teoria por trás da computação quântica. Para um estudo mais aprofundado do assunto, os livros e artigos nas referências bibliográficas deste texto podem ser consultados.</p><h4>Bibliografia</h4><ul><li>Livro <strong>Quantum Computing and Quantum Information</strong>, dos autores <strong>Michael A. Nielsen</strong> e <strong>Isaac L. Chuang</strong>. Publicado pela editora <strong>Cambridge University Press</strong>. Informações disponíveis em <a href="https://www.cambridge.org/core/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE">https://www.cambridge.org/core/books/quantum-computation-and-quantum-information/01E10196D0A682A6AEFFEA52D53BE9AE</a> (acesso em 27 jun 2020)</li><li>Livro <strong>Mastering Quantum Computing with IBM QX</strong>, da autora <strong>Dr. Christine Corbett Moran</strong>. Publicado pela editora<strong> Packt</strong>. Informações disponíveis em <a href="https://www.packtpub.com/application-development/mastering-quantum-computing-ibm-qx">https://www.packtpub.com/application-development/mastering-quantum-computing-ibm-qx</a> (acesso em 27 jun 2020)</li><li>Monografia <strong>Uma Introdução à Computação Quântica</strong>, dos autores <strong>André Luís Vignatti</strong>, <strong>Francisco Summa Netto</strong> e <strong>Luiz Fernando Bittencourt</strong>. Defendida no<strong> Departamento de Informática da Universidade do Paraná</strong>. Disponível em <a href="https://www.ic.unicamp.br/~bit/arquivos/tg.pdf">https://www.ic.unicamp.br/~bit/arquivos/tg.pdf</a> (acesso em 27 jun 2020)</li><li>Artigo <strong>Uma Introdução aos Algoritmos Quânticos</strong>, dos autores <strong>Renato Portugal </strong>(<strong>LNCC</strong>), <strong>Carlile C. Lavor</strong> (<strong>IME-UERJ</strong>), <strong>Luiz M. Carvalho</strong> (<strong>IME-UERJ</strong>) e <strong>Nelson Maculan </strong>(<strong>COPPE-UFRJ</strong>).</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=22763e797b8d" width="1" height="1" alt=""><hr><p><a href="https://medium.com/programadores-ajudando-programadores/uma-introdu%C3%A7%C3%A3o-%C3%A0-matem%C3%A1tica-da-computa%C3%A7%C3%A3o-qu%C3%A2ntica-22763e797b8d">Uma introdução à matemática da computação quântica</a> was originally published in <a href="https://medium.com/programadores-ajudando-programadores">Programadores Ajudando Programadores</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Grafos e algoritmos]]></title>
            <link>https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/697c1fd4a416</guid>
            <category><![CDATA[estruturadedados]]></category>
            <category><![CDATA[teoria-dos-grafos]]></category>
            <category><![CDATA[estruturas-de-dados]]></category>
            <category><![CDATA[matemática]]></category>
            <category><![CDATA[ciência-da-computação]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Mon, 13 Apr 2020 11:33:13 GMT</pubDate>
            <atom:updated>2022-05-17T13:16:22.752Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/482/1*3I4EADaAAWh6K27R25bLkQ.png" /><figcaption>grafo de um autômato finito não determinístico generalizado (AFNG)</figcaption></figure><h3>Capítulo 1 — Introdução</h3><p>Os grafos estão presentes em muito do que diz respeito à ciência da computação. Eles são uma abstração perfeitamente computável para boa parte das relações da realidade e da imaginação humana.</p><p>Conceitualmente, um grafo é composto por um conjunto discreto de elementos que representam a existência de algo material ou imaginário. Estes elementos se relacionam; há uma regra, ou um conjunto de regras, definindo estas relações pela lógica. Em outras palavras, os elementos do conjunto discreto em questão são inter-conectados por relações de um padrão de incidência bem definido, e estas relações fazem parte do grafo — elas são expressas por <strong>arestas</strong>, enquanto os elementos inter-conectados são expressos por <strong>vértices</strong>.</p><p>Você pode inquirir por esclarecimento: a propósito, o que exatamente significa isso? Qual é a aplicação prática disso tudo? Para que estas dúvidas se façam sanadas, é conveniente que antes se conheça alguns formalismos sobre os grafos. A concepção deste universo de idéias com vértices e arestas é papel de uma teoria matemática prenunciada por <strong>Leonhard Euler </strong>em 1736, em seu artigo sobre o <strong>problema das 7 pontes de Königsberg.</strong> É a chamada <strong>teoria dos grafos</strong>.</p><p>Basicamente, a <strong>teoria dos grafos</strong> trata de relações entre elementos de conjuntos discretos. Ela é amplamente empregada em algoritmos para abstrair objetos do mundo real ou imaginário que são inter-relacionados de alguma forma.</p><h3>Capítulo 2 — Teoria matemática dos grafos</h3><h4>2.1 Elementos de um grafo</h4><p>Um Grafo é constituído por um conjunto de <strong>vértices</strong>, um conjunto de <strong>arestas</strong> e uma <strong>função de incidência</strong>.</p><ul><li><strong>Os vértices </strong>são elementos, inter-relacionados de alguma forma, pertencentes a um conjunto discreto (enumerável).</li><li><strong>As arestas </strong>são elementos de um conjunto discreto que descrevem, de alguma forma, as relações entre os vértices do grafo.</li><li><strong>A função de incidência </strong>é uma função que mapeia, para cada aresta do grafo, um par de vértices envolvidos no relacionamento.</li></ul><p>Grafos normalmente são representados graficamente por diagramas, onde os vértices são pontos e as arestas são linhas (ou setas, no caso dos dígrafos) que ligam os pontos dos respectivos vértices envolvidos no relacionamento.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*V06GANelvn1mW10UNcSMtw.png" /><figcaption>Representação gráfica de um grafo não direcionado formado pelos vértices <strong>{A, B, C, D}</strong> e pelas arestas <strong>{1, 2, 3, 4}</strong>.</figcaption></figure><p>No grafo da figura acima, temos um conjunto de vértices <strong><em>VG = {A, B, C, D}</em></strong>, e um conjunto de arestas <strong><em>aG = {1, 2, 3, 4}</em></strong>. A função de incidência <strong>ΨG</strong> mapeia as relações do conjunto de arestas da seguinte forma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/290/1*NMBKi7Bs0NxkAZfehPeLOQ.png" /><figcaption>Resposta da função de incidência para cada aresta do grafo apresentado acima</figcaption></figure><p>Estes elementos do grafo podem ter diversas interpretações. Se estivéssemos representando um <strong>mapa urbano</strong>, os vértices poderiam ser as casas e as arestas poderiam ser as vias de mão dupla que interligam estas casas. Em outro exemplo: se estivéssemos representando uma rede social, os vértices poderiam ser pessoas e as arestas poderiam ser as relações de amizade entre elas. Perceba que em ambos estes casos as relações são mútuas.</p><ul><li>No exemplo da rede social: Se houver uma relação de amizade entre duas pessoas, então ambas se conhecem e consideram-se amigas.</li><li>No exemplo do mapa: Se houver uma via de mão dupla interligando duas casas, qualquer veículo pode se locomover para qualquer uma das duas casas por meio desta via.</li></ul><p>Porém, há casos em que as relações do grafo não são mútuas. Se estivéssemos, por exemplo, representando um mapa (semelhante ao mapa do exemplo anterior), com ruas de mão única (onde os veículos só podem circular em um sentido), a ideia de relação mútua no grafo já não serviria mais. Outro exemplo: se estivéssemos representando uma rede social como o <em>Twitter</em> ou o <em>Instagram</em>, em que as relações de amizade são substituídas por relações de “seguidor” e “seguido” (e uma pessoa não é obrigada a seguir seus seguidores), a ideia de relação mútua no grafo também não serviria.</p><h4>2.2 Dígrafos</h4><p>O fato de que pode ser necessário representar relações não mútuas com grafos justifica a existência de duas categorias de grafos:</p><ul><li><strong>Grafos não-direcionados</strong>: Grafos cujas arestas representam relações mútuas.</li><li><strong>Grafos direcionados</strong> (também chamados de <strong>dígrafos</strong>): Grafos cujas arestas possuem direção definida e representam relações não necessariamente mútuas.</li></ul><p>Na representação gráfica do dígrafo, as arestas são representadas como setas que indicam uma ou duas direções, ao invés de linhas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*0-SFD6dRJhS9obeUgTMFOw.png" /><figcaption>Representação gráfica de um dígrafo formado pelos vértices <strong>{A, B, C, D}</strong> e pelas arestas direcionadas <strong>{1, 2, 3, 4}.</strong></figcaption></figure><p>É possível representar um mapa com vias de mão única, ou uma rede social como o <em>Twitter</em> ou o <em>Instagram</em>, utilizando um dígrafo, por conta de suas relações, que não necessariamente são mútuas.</p><h4>2.3 Grafos valorados</h4><p>Grafos valorados, ou grafos ponderados, são grafos cujas arestas contêm pesos. Estes são utilizados para representar alguma caraterística escalar do relacionamento correspondente.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*d39YIBc1W-VZp6-uX5O_yA.png" /><figcaption>Representação gráfica de um dígrafo formado pelos vértices <strong>{A, B, C, D}</strong> e pelas arestas direcionadas ponderadas <strong>{1, 2, 3, 4}</strong>. Os pesos das arestas estão em marrom, enquanto a numeração esta em vermelho.</figcaption></figure><p>Os pesos podem ser utilizados para indicar uma medida de custo ou grandeza da incidência da relação correspondente. No exemplo do mapa urbano, os pesos podem representar o comprimento das vias, a dificuldade de locomoção na via, ou um produto desses dois fatores.</p><h4>2.4 Grafos nulos</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*SfJ8OI6Uwb5jmmfydsT79g.png" /><figcaption>Grafo nulo de 4 vértices</figcaption></figure><p>Por definição, um grafo é <strong>nulo</strong> quando não possui arestas (mesmo que possua vértices).</p><h4>2.5 Grafos completos</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*tANwzUKAFcKnDk9UJnyPog.png" /><figcaption>Grafo completo de 5 vértices</figcaption></figure><p>Por definição, um grafo é <strong>completo</strong> quando todos os seus possíveis pares de vértices são conectados por uma aresta.</p><h4>2.6 Grafos regulares</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/452/1*Gmsk4R_GDrBZz7hBitt6_w.png" /><figcaption>Grafo regular de grau 5 (5-regular).</figcaption></figure><p>Por definição, um grafo é <strong>k-regular</strong> quando todos os seus vértices são conectados pela mesma quantidade <strong>k</strong> de arestas. Em outras palavras, se todos os vértices do grafo possuem o mesmo grau<strong> k</strong>, o grafo é um <strong>k-regular</strong> (de grau <strong>k</strong>).</p><h4>2.7 Subgrafos</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*UPBTdeVbcQxyQxOy_mx0kw.png" /><figcaption>Da esquerda para a direita, respectivamente, um grafo e um de seus subgrafos.</figcaption></figure><p>O conceito de subgrafo é análogo à definição de subconjunto. Suponha que, na imagem acima, o grafo da esquerda é <strong>G</strong> e o grafo da direita é <strong>H</strong>. Quando um grafo <strong>H</strong> está contido em um grafo <strong>G</strong>, diz-se que <strong>H</strong> é subgrafo de <strong>G</strong>. Em outras palavras: Se o conjunto de vértices de <strong>H</strong> é subconjunto dos vértices de <strong>G</strong>, o conjunto de arestas de <strong>H</strong> é subconjunto das arestas de <strong>G</strong>, e esses vértices estão interconectados em <strong>H</strong> da mesma forma que estão em <strong>G</strong>, então <strong>H</strong> é subgrafo de <strong>G</strong>.</p><h4>2.8 Laços</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/154/1*pA2teewSzFSZY96UScVXww.png" /><figcaption>Vértice conectado a si próprio por um laço</figcaption></figure><p>Por definição, uma aresta que conecta um vértice a ele mesmo é chamada de <strong>laço</strong>.</p><h4>2.9 Ciclos</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/518/1*tNYXJfPiP4PW5a8LKnoASw.png" /><figcaption>Grafo ciclo de 5 vértices</figcaption></figure><p>Um ciclo é um grafo onde todos os pares possíveis de vértices são conectados por uma aresta, e todos os vértices possuem 2 conexões. Em outras palavras, um grafo conexo de grau 2 é, por definição, um ciclo.<br>Um grafo que possui um ou mais ciclos em seus subgrafos caracteriza-se por formar caminhos pelos quais é possível voltar ao vértice de partida. É necessário ter cuidado com este tipo de grafo na programação, pois os ciclos podem ser problemáticos para alguns algoritmos.</p><h3>Capítulo 3 — Estruturas de dados</h3><h4>3.1 Estruturas de dados</h4><p><strong>Estruturas de dados (EDs) </strong>— que são o tema da abordagem deste capítulo — são basicamente formas particulares de organizar dados na memória de um computador. É bastante comum que organizações de dados compostas por elementos de conjuntos discretos e relacionamentos sejam utilizadas em programas de computador. Algoritmos como <strong>listas encadeadas</strong> e <strong>árvores binárias</strong> utilizam esta lógica para agrupar dados dispersos na memória do computador de forma que estes possam ser manipulados com alguma eficiência.</p><h4>3.2 Modelos</h4><p>Criar um programa de computador é um processo, e algumas etapas deste processo acontecem antes da codificação. De modo geral, uma fase de idealização do programa deve preceder a codificação, e esta fase pode ser concebida de diversas formas: Ela pode ser exercida por um engenheiro de software, por um cientista, ou pelo próprio programador, e pode ter um registro — uma lista de requisitos, um diagrama, um fluxograma ou até uma representação em linguagem matemática.</p><p>A fase de idealização do programa pode envolver a projeção de uma representação esquemática e fácil de entender do que deverá ser implementado na fase de codificação — o <strong>modelo</strong>. Aqui partimos de uma tediosa abordagem puramente teórica para algo mais “palpável”: Para uma boa parte dos algoritmos que lidam com o que chamamos de <strong>estruturas de dados</strong>, os modelos são, basicamente, grafos.</p><h4>3.3 Sobre termos não muito formais</h4><p>Quando se trata de algoritmos e programação de computadores, o que é conhecido como “vértice” ou “aresta” na teoria dos grafos, costuma ser chamado de “nó”, “item” ou “elemento”, mesmo porque a teoria é só uma abstração da prática, e estas aplicações não precisam estar totalmente de acordo com as definições matemáticas de grafos. Neste texto, frequentemente será usado o termo “elemento” para se referir a algo que pode ser um vértice ou uma aresta de um grafo.</p><h4>3.4 EDs básicas — Listas Encadeadas e Árvores</h4><p>Existem dois modelos de algoritmos baseados em grafos que são muito corriqueiros na programação de computadores:</p><ul><li><strong>Listas encadeadas</strong> são frequentemente empregadas na criação de arranjos dinâmicos lineares de elementos. Este modelo de ED possibilita que dados sejam agrupados em um arranjo que admite inserções e remoções de elementos com pouco custo computacional.</li><li><strong>Árvores</strong> são frequentemente empregadas na criação de arranjos dinâmicos não lineares de elementos. Este modelo possibilita que dados sejam agrupados com uma regra de ordenamento definida, admitindo inserções e remoções de elementos com pouco custo. Algumas variações de árvores também podem ser utilizadas para organizar famílias de dados (é o que acontece, por exemplo, em um sistema de arquivos e diretórios).</li></ul><p>Estes dois modelos de EDs são muito conhecidos e utilizados, tidos praticamente como conceitos básicos de ciência da computação, e suas aplicações geralmente não requerem grandes reinvenções, apenas pequenas adaptações. Ambos possuem diversas implementações disponíveis ao publico, que podem ser facilmente encontradas com rápidas buscas no <em>Google</em> ou no <em>GitHub.</em></p><p>Estes modelos não são os únicos possíveis, nem os únicos necessários. Por mais versáteis que sejam, as vezes é — sim — necessária uma mudança radical na forma como estes são implementados ou aplicados. Também há casos nos quais é necessário que se utilize um modelo menos corriqueiro e mais específico para uma determinada aplicação, ou até mesmo que se crie um novo modelo.</p><h4>3.5 Lista encadeada</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/677/1*Nqja8LVKRPUeQMDt0JAdOg.png" /><figcaption>Representação gráfica de uma lista encadeada simples</figcaption></figure><p>Uma <strong>lista encadeada</strong> é uma estrutura de dados linear. Nela, os elementos do conjunto são associados por relações de “posterior” ou “anterior”, na intenção de criar uma espécie de fileira imaginária.</p><h4>3.6 Árvore</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/418/1*wCv4FDMPOba8zISa5W0csQ.png" /><figcaption>Representação gráfica de uma árvore binaria</figcaption></figure><p>As <strong>árvores</strong> são estruturas de dados não lineares, nas quais os elementos costumam ser associados por relações de “esquerdo”, “direito”, “inferior”, “superior”, “pai”, “filho”, “menor”, “maior”, etc. Estas estruturas formam grafos <strong>conexos</strong> e <strong>acíclicos</strong>. Quando representados graficamente, formam diagramas que remetem à estrutura física de uma árvore (da natureza), com galhos ramificados.</p><h3>Capítulo 4 — Vértices e arestas em estruturas de dados</h3><h4>4.1 Registros, objetos e referências</h4><p>Em estruturas de dados como <strong>listas encadeadas</strong> e <strong>árvores</strong> os vértices do modelo costumam ser implementados como registros ou objetos, contendo informações do elemento correspondente. Dentro desses registros ou objetos, costumam haver referências para outros elementos do mesmo conjunto: Estas referências fazem o papel das <strong>arestas</strong> do grafo.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/41286d40d5647d77843014a5bafecc4a/href">https://medium.com/media/41286d40d5647d77843014a5bafecc4a/href</a></iframe><p>Repare que, no algoritmo apresentado acima, a classe <strong>NodoLista</strong> define a estrutura padrão dos elementos da lista encadeada. Esta classe possui dois atributos: <strong>dado</strong> e <strong>próximo</strong>. O atributo <strong>dado</strong> deve conter uma informação qualquer (como o meu nome), e o atributo <strong>próximo</strong> deve conter uma referência para o objeto <strong>NodoLista</strong> do elemento adjacente (ou <strong>None</strong>, caso não haja elemento adjacente).</p><h4>4.2 Listas de adjacências</h4><p>Programar grafos fora dos moldes das listas encadeadas e árvores utilizando arranjos/registros/classes e referências nem sempre é conveniente. Uma outra maneira simples de representar um grafo em linhas de código é criar uma estrutura que contenha uma lista de adjacências para cada vértice do grafo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/463/1*V06GANelvn1mW10UNcSMtw.png" /><figcaption>Um grafo qualquer (que você já viu na segunda seção deste texto)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/242/1*Bx54uBGNQWW1bqws9nYAcw.png" /><figcaption>Adjacências dos vértices do grafo da imagem acima</figcaption></figure><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/156fd370cd6b1f004d577f7bf3f3ddf2/href">https://medium.com/media/156fd370cd6b1f004d577f7bf3f3ddf2/href</a></iframe><p>Neste algoritmo, foi criado um dicionário com uma lista de adjacências para cada vértice do grafo.</p><p>O dicionário é um recurso da linguagem <em>Python</em> que facilita bastante nosso trabalho, pois permite que as listas de adjacências sejam indexadas com <em>strings</em> ao invés de números naturais, mas isso não significa que esta técnica de programação não possa ser reproduzida em outras linguagens.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/b497307747f25d5ffb27dfafc3dad7f6/href">https://medium.com/media/b497307747f25d5ffb27dfafc3dad7f6/href</a></iframe><h3>Capítulo 5— Buscando elementos específicos em grafos</h3><p>Imagine uma situação na qual, lidando com uma coleção de dados dispersos na memória do computador, seja necessário obter um ou mais elementos desta coleção que atendam a um determinado padrão. Isto é, categoricamente, um problema de <strong>busca</strong>, e existem duas formas conhecidas de resolvê-lo no âmbito computacional dos grafos: <strong>Busca em profundidade</strong> e <strong>busca em largura</strong>. Ambas as soluções serão explicadas.</p><h4>5.1 Busca em profundidade</h4><p>A busca em profundidade é uma estratégia utilizada para buscar elementos específicos em grafos. Esta técnica faz uso de <strong>funções recursivas</strong>, e funciona muito bem com <strong>grafos árvore</strong>.</p><p>A função recursiva de busca deve desempenhar o seguinte processo:</p><p>1 — Obter o elemento recebido como argumento</p><p>2 — Verificar se o elemento obtido é o elemento procurado:</p><ul><li><strong>Caso seja</strong>, o escopo corrente da função recursiva deve retornar este elemento</li><li><strong>Caso não seja</strong>, o processo continua</li></ul><p>3 — Obter os elementos adjacentes do elemento recebido como argumento</p><p>4 — Para cada um dos elementos adjacentes, fazer uma chamada recursiva passando o respectivo elemento como argumento</p><p>5 — Verificar se alguma das chamadas recursivas retornou o elemento procurado:</p><ul><li><strong>Se sim</strong>, o escopo corrente da função recursiva deve retornar este elemento</li><li><strong>Se não</strong>, o escopo corrente da função recursiva deve retornar um dado que indique que o elemento buscado não foi encontrado.</li></ul><p>Para um grafo árvore <strong>G</strong>, considere uma função de busca em profundidade <strong>R = b(E)</strong>, onde <strong>E</strong> é um elemento (vértice) da árvore e <strong>R</strong> é o elemento que <strong>b(E)</strong> retornou. O procedimento de <strong>R = b(E)</strong> pode ser descrito com o seguinte fluxograma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/539/1*vp7WXGKU2jpamId0R1fbUA.png" /><figcaption>Fluxograma da função de busca em profundidade <strong>R = b(E)</strong></figcaption></figure><p>Para fins de demonstração, considere que estamos trabalhando com uma árvore formada por objetos de uma classe chamada <strong>NodoArvore</strong>, com os seguintes atributos:</p><ul><li><strong>nome</strong>: Contém o nome de uma pessoa;</li><li><strong>id</strong>: Contém o número identificador da pessoa;</li><li><strong>menor</strong>: Contém uma referência para outro objeto com um número identificador menor (ou <strong>None</strong>, caso não haja adjacência);</li><li><strong>maior</strong>: Contém uma referência para outro objeto com um número identificador maior (ou <strong>None</strong>, caso não haja adjacência).</li></ul><p>A classe <strong>NodoArvore</strong> também tem um método chamado <strong>inserir</strong>, que insere novos objetos na árvore recursivamente, e um método chamado <strong>imprimir</strong>, que imprime no <em>prompt</em> uma mensagem com os valores contidos no objeto para os atributos <strong>nome</strong> e <em>id</em>.</p><p>Veja, no próximo algoritmo, uma possível implementação para esta classe.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/527e92c6c68df3a4420fa04ec01f0661/href">https://medium.com/media/527e92c6c68df3a4420fa04ec01f0661/href</a></iframe><p>Podemos facilmente criar um algoritmo que acessa todos os elementos desta arvore utilizando uma função recursiva. Veja no exemplo a seguir.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/a2198476c6d0dcea5f2b3b33789d9ce3/href">https://medium.com/media/a2198476c6d0dcea5f2b3b33789d9ce3/href</a></iframe><p>A função <strong>percorrer_arvore</strong> invoca o método <strong>imprimir</strong> para cada um dos objetos da árvore, e uma lista com todos os nomes e <em>ids</em> da árvore é impressa (com os <em>ids</em> em ordem crescente).<br> <br> É possível criar uma função recursiva que busca um determinado valor na árvore e retorna o objeto <strong>NodoArvore</strong> onde o valor foi encontrado.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/db8f152efbd2c09eb4dfdd7ec993c1f9/href">https://medium.com/media/db8f152efbd2c09eb4dfdd7ec993c1f9/href</a></iframe><p>Quando a função <strong>buscar </strong>é invocada, recebendo como argumento a raiz da árvore e um nome contido em um dos elementos desta, uma <strong>busca em profundidade</strong> é feita na arvore, e o objeto no qual o nome foi encontrado é retornado. Quando o nome não é encontrado na árvore, a função retorna <strong>None</strong>.<br> <br> A busca em profundidade percorre os elementos da árvore “de cima para baixo” (ou “de baixo para cima”), em sequências de profundidade crescente ou decrescente. Quando um elemento da árvore é acessado e termina de ser avaliado pela busca, antes de verificar os outros elementos do mesmo nível da arvore, o algoritmo percorre os elementos de profundidade mais baixa ou mais alta. Este “mergulho” nos níveis da árvore (que normalmente acontece várias vezes em uma busca) termina quando, em uma de suas chamadas recursivas, a função atinge uma extremidade da árvore.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/874/1*0Rj_kOGfPO2sNreo4lESGw.png" /><figcaption>Exemplo de sequência de verificações que um algoritmo de busca em profundidade pode fazer em uma árvore binária</figcaption></figure><p>No entanto, se esta técnica for aplicada a um grafo que contenha ciclos, a recursão entrará em uma cadeia de acessos repetidos a determinados objetos da estrutura e, por fim, acontecerá uma falha conhecida como <strong>estouro de pilha</strong> (<em>“stack overflow”</em>, em inglês). É necessário, nestes casos, usar algum artifício para “marcar” os objetos que já foram acessados durante a busca, para que o algoritmo não verifique um objeto mais de uma vez durante a busca.</p><h4>5.2 Busca em largura</h4><p>A busca em largura é uma estratégia de busca em grafos na qual, após a verificação de um elemento do grafo, todos os elementos ajacentes são obtidos e verificados. Esta estratégia não possui o mesmo problema que a busca em profundidade com relação aos grafos cíclicos, embora também apresente algumas fragilidades que serão citadas mais adiante.</p><p>O artifício utilizado para desempenhar a busca em largura é um algoritmo de <strong>fila</strong>. Após o primeiro elemento do grafo ser verificado, todos os elementos adjacentes são obtidos e inseridos na fila. A execução do algoritmo prossegue em sucessivas repetições do seguinte processo:</p><p>1 — Obter (e remover da fila) o elemento que está a mais tempo na fila</p><p>2 — Verificar se o elemento obtido é o elemento procurado:</p><ul><li><strong>Caso seja</strong>, a sucessão de repetições é finalizada</li><li><strong>Caso não seja</strong>, o processo continua</li></ul><p>3 — Obter os elementos adjacentes do último elemento obtido</p><p>4 — Inserir na fila todos os elementos adjacentes obtidos</p><p>Para um grafo <strong>G</strong>, considere uma função de busca em largura <strong>R = b(E)</strong>, onde <strong>E</strong> é um elemento (vértice) do grafo e <strong>R</strong> é o elemento que <strong>b(E)</strong> retornou. O procedimento de <strong>R = b(E)</strong> pode ser descrito com o seguinte fluxograma:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/388/1*WGO4fMBYHMw1nD4Cb3W6Ag.png" /><figcaption>Fluxograma da função de busca em largura <strong>R = b(E)</strong></figcaption></figure><p>Para demonstrar esta técnica, será apresentado um algoritmo de busca em largura para o seguinte dígrafo:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/320/1*DSXRhKpebyFm3pnbHgKCFw.png" /><figcaption>Dígrafo de exemplo</figcaption></figure><p>Este dígrafo foi implementado com uma classe chamada <strong>Elemento</strong>, que possuí os seguintes atributos:</p><ul><li><strong>Cor:</strong> Contém a cor do elemento no grafo.</li><li><strong>Adjacências:</strong> Contém uma lista de elementos adjacentes.</li></ul><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/871a5fda5a39208e49fe2fc87d0f0674/href">https://medium.com/media/871a5fda5a39208e49fe2fc87d0f0674/href</a></iframe><p>É possível implementar uma função para buscar (utilizando uma busca em largura) o elemento de uma determinada cor no grafo da seguinte forma:</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/4be7aab98aec58411e8c6411ced28ca2/href">https://medium.com/media/4be7aab98aec58411e8c6411ced28ca2/href</a></iframe><p>A função <strong>buscar</strong>, do algoritmo 2.7, deve receber como argumento um objeto <strong>Elemento</strong> qualquer do grafo (a partir do qual a busca iniciará) e a cor do elemento procurado.<br> <br> No entanto, esta implementação tem dois problemas:</p><p>1 — Caso o elemento procurado não exista no grafo, o procedimento entrará em um <em>loop</em> infinito, causando o travamento da aplicação.<br> 2 — Caso o grafo seja cíclico, possivelmente ocorrerá reinserções de objetos (que já foram verificados) na fila, o que é desnecessário e implica em desperdício de memória.</p><p>Estes dois problemas podem ser corrigidos se, na implementação da função <strong>buscar</strong>, a seguinte regra for definida:</p><p><strong>Um objeto só pode ser inserido na fila caso:</strong></p><p>1 — Ele ainda não tenha sido verificado;<br>2 — Ele não esteja na fila esperando para ser verificado.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/528/1*6JgELxzqaIYRMnzOnobFTg.png" /><figcaption>Fluxograma da função de busca em largura <strong>R = b(E)</strong> com a nova regra.</figcaption></figure><p>A primeira condição da regra pode ser implementada se todos os objetos verificados forem inseridos em uma lista. Neste caso, é possível saber se um objeto já foi verificado conferindo se ele está contido nesta lista.</p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/28c06361784d2f8e7d13302f9cbd7f02/href">https://medium.com/media/28c06361784d2f8e7d13302f9cbd7f02/href</a></iframe><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*3LKkxHv69nqwjA9qaUtjzw.png" /><figcaption>Etapas do trabalho da busca em largura</figcaption></figure><h3>Capítulo 6 — Problema do menor caminho</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/300/1*RQPwz3BgwVAk9ndNZH1fXA.png" /></figure><p>Para abrir o capítulo, uma situação cotidiana será ilustrada: Imagine que você, leitor, está saindo do trabalho ou da faculdade após um longo e chuvoso dia. A tempestade, que durante toda a tarde lhe atordoou com o barulho das fortes trovoadas e rajadas de vento, deixou para o fim do dia alguns rastros de destruição espalhados pela cidade: Causou alagamentos, acidentes, quedas de arvores e obstrução de muitas vias públicas. Este inconveniente todo culminou em longos congestionamentos nas principais avenidas da cidade (pelas quais você normalmente passa voltando para sua residência). O trânsito está terrível!</p><p>Com medo de passar horas nos lentos engarrafamentos a caminho de casa, você toma uma atitude antes de sair: Procura e instala um aplicativo em seu <em>smartphone</em> que irá determinar o caminho mais rápido para sua casa. Ao abrir o aplicativo, um serviço identifica sua localização por meio do GPS, obtém as informações do trânsito na região, solicita que um local de destino seja especificado e, por fim, determina a rota que você deverá seguir com seu carro para chegar em casa sem perder muito tempo nos congestionamentos.</p><p>Problema resolvido! O caminho mínimo entre sua localização atual e sua casa foi encontrado por um algoritmo de <strong><em>path-finding</em></strong>, e agora você poderá voltar para casa tranquilamente.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/561/1*Mojd_PCqT_b-7lj1humA0Q.png" /><figcaption>Google Maps resolvendo um problema de menor caminho</figcaption></figure><p>Este é um dos problemas que podem ser resolvidos utilizando algoritmos de busca em grafos: O <strong>problema do menor caminho</strong> (também conhecido como <strong><em>path-finding</em></strong> em inglês). Resolver este problema consiste em encontrar o caminho mais curto ou menos custoso de um vértice do grafo a outro. Existem vários algoritmos de <em>path-finding</em>, e neste capítulo serão brevemente abordados dois deles: O algoritmo de <strong><em>Dijkstra</em></strong> e o algoritmo <strong>A*</strong> (a-estrela).</p><h4>6.1 Algoritmo de Dijsktra</h4><p>O algoritmo de <em>Dijkstra</em>, assim como qualquer algoritmo de <em>path-finding</em>, deve receber, antes de começar a busca, dois parâmetros: Um elemento inicial e elemento final do grafo. O algoritmo deverá responder com uma lista encadeada constituída pelos elementos do grafo contidos no caminho mínimo entre o elemento inicial e o elemento final.</p><p>Considere a representação do algoritmo de <em>Dijkstra</em> como uma função <strong><em>C = dijkstra(Vi, Vf)</em></strong>, onde:</p><ul><li><strong><em>Vi</em></strong> é o elemento vértice inicial do caminho.</li><li><strong><em>Vf</em></strong> é o elemento vértice final do caminho.</li><li><strong><em>C</em></strong> é o caminho mínimo entre <strong><em>Vi</em></strong> e <strong><em>Vf</em></strong><em>.</em></li></ul><p>A implementação do algoritmo de <em>Dijkstra</em> se assemelha em alguns aspectos à implementação de uma busca em profundidade. Tal como a busca em profundidade, o algoritmo de <em>Dijkstra</em> é um algoritmo <strong>iterativo</strong>, ou seja, ele desempenha a busca em um longo processo repetitivo. Em contraste com a busca em profundidade, o algoritmo de <em>Dijkstra</em> utiliza uma <strong>fila de prioridade</strong> ao invés de uma fila simples. A <strong>fila de prioridade</strong> é uma estrutura de agrupamento de dados na qual cada elemento é associado a um valor numérico chamado <strong>chave</strong>. A ordem na qual os elementos na fila de prioridade são obtidos e removidos ocorre de acordo com o valor chave de cada um destes elementos. No algoritmo de <em>Dijkstra</em>, as iterações obtêm vértices do grafo e calculam suas distâncias (ou custo acumulativo) para o vértice de origem <strong><em>Vi</em></strong> até que vértice final <strong><em>Vf</em></strong> seja encontrado. Cada vez que um vértice é obtido e tem sua distância para o <strong><em>Vi</em></strong> calculada, é inserido na fila de prioridade, e sua distância para <strong><em>Vi</em></strong> é usada como chave. Aí entra o papel da fila de prioridade: a cada iteração, para obter os próximos vértices do grafo que deverão ser analisados, o algoritmo busca o vértice na fila com menor chave (ou seja, menor distância para <strong><em>Vi</em></strong>) e obtém seus vértices adjecentes para processar. Com o auxílio de um conjunto de operações de lista encadeada, uma sequência de nós contendo vértices vai sendo gerada ao longo da execução do algoritmo e ligada de acordo com as adjacencias dos vértices. Ao fim da execução do algoritmo, quando o vértice <strong><em>Vf </em></strong>for encontrado, haverá uma lista encadeada correspondente a <strong><em>C </em></strong>(o menor caminho entre <strong><em>Vi</em></strong> e <strong><em>Vf</em></strong><em>).</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/210/1*2jRCHqAbTCY7W7oG5ntMOQ.gif" /><figcaption>Demonstração do trabalho do algoritmo de Dijkstra para encontrar o caminho de um robô até o ponto verde em um ambiênte com obstáculos. Fonte: <a href="https://commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif">https://commons.wikimedia.org/wiki/File:Dijkstras_progress_animation.gif</a></figcaption></figure><h4><strong>6.2 Algoritmo A*</strong></h4><p>O algoritmo de <em>Dijkstra</em> é bastante custoso e pode não ser uma solução viável em algumas situações por conta do tempo que ele leva para dar uma resposta. Uma alternativa menos custosa ao algoritmo de <em>Dijkstra</em> é o algoritmo <strong>A*</strong> (<em>a-star</em>). Este algoritmo se assemelha muito ao algoritmo de <em>Dijkstra.</em> A diferênça do algoritmo <strong>A*</strong> para o algoritmo de <em>Dijkstra</em> está no fato de que o algoritmo <strong>A*</strong> usa uma <strong>heurística</strong> para otimizar o processo de busca pelo menor caminho. Esta <strong>heurística</strong> é basicamente uma estimativa da distância de um vértice <strong><em>V </em></strong>qualquer do grafo para o vértice final <strong><em>Vf</em></strong>. No algoritmo <strong>A*</strong>, a chave dos vértices na fila são calculadas como a soma da distância exata para <strong><em>Vi</em></strong> com a distância heurística para <strong><em>Vf</em></strong>. Consequentemente, o algoritmo sempre obterá para análise os vértices que provavelmente estão mais próximos de <strong><em>Vf</em></strong> em cada iteração, e precisará analisar menos vértices do que o algoritmo de <em>Dijsktra</em> para encontrar o caminho mínimo entre <strong><em>Vi</em></strong> e <strong><em>Vf</em></strong>.</p><p>Quanto menos errática for a heurística, menos custoso será o trabalho do algoritmo.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/210/1*2lZWsHr2pUBvct34qGUL1Q.gif" /><figcaption>Demonstração do trabalho do algoritmo <strong>A*</strong> para encontrar o caminho de um robô até o ponto verde em um ambiênte com obstáculos. Fonte: <a href="https://commons.wikimedia.org/wiki/File:Weighted_A_star_with_eps_5.gif">https://commons.wikimedia.org/wiki/File:Weighted_A_star_with_eps_5.gif</a></figcaption></figure><h3>Referências</h3><ul><li>Livro: <strong>Grafos — Uma Introdução</strong>, de <strong>Samuel Jurkiewicz.</strong></li><li><strong>Capítulo 3</strong> do livro: <strong>Inteligência Artificial</strong>, de <strong>Stuart Russell</strong> e <strong>Peter Norvig. </strong>Terceira edição, traduzida por <strong>Regina Célia Simille de Macedo</strong>. Editoras: <strong>Elsevier</strong> e <strong>Campus</strong>.</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=697c1fd4a416" width="1" height="1" alt=""><hr><p><a href="https://medium.com/programadores-ajudando-programadores/os-grafos-e-os-algoritmos-697c1fd4a416">Grafos e algoritmos</a> was originally published in <a href="https://medium.com/programadores-ajudando-programadores">Programadores Ajudando Programadores</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[UNIX, o pai dos sistemas operacionais modernos]]></title>
            <link>https://medium.com/programadores-ajudando-programadores/a-hist%C3%B3ria-do-unix-o-pai-dos-sistemas-operacionais-modernos-2795d0fd564b?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/2795d0fd564b</guid>
            <category><![CDATA[sistemas-operacionais]]></category>
            <category><![CDATA[unix]]></category>
            <category><![CDATA[minix]]></category>
            <category><![CDATA[linux]]></category>
            <category><![CDATA[bsd]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Sun, 20 Jan 2019 08:23:46 GMT</pubDate>
            <atom:updated>2020-10-24T03:55:31.372Z</atom:updated>
            <content:encoded><![CDATA[<h4>Lançado pela primeira vez em 1969, é conhecido até hoje como um dos sistemas operacionais mais importantes da história.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*WpIUfFHDhpr7PmmdfiHWGw.jpeg" /><figcaption>Dennis Ritchie e Ken Thompson sentados em frente a um computador PDP-11. Crédito da foto: dmr (fonte: <a href="http://thetamnews.org/opinion/dennis-ritchie-computer-scientist-dies-at-70/">http://thetamnews.org/opinion/dennis-ritchie-computer-scientist-dies-at-70/</a> )</figcaption></figure><p>Sistemas operacionais têm por objetivo estabelecer uma camada de abstração entre hardware e software, tirando o encargo do programador de trabalhar diretamente com as especificidades da arquitetura do computador em questão. Eles tornam os computadores mais fáceis de operar, tanto para os programadores como para os usuários.</p><p>O sistema operacional UNIX possui recursos interessantes implementados de maneira relativamente simples. Nele, foi implementada de forma bem sucedida a operação com múltiplos usuários e múltiplos processos simultâneos. Também possui uma arquitetura modular, permitindo que componentes de software sejam adicionados e removidos dinamicamente em sua integralidade, eliminando a necessidade de recompilar o código fonte do sistema inteiro sempre que um novo módulo precisa ser incluído. Além disso, ele pode ser adaptado para diferentes computadores de forma relativamente fácil, por ser programado em linguagem C.</p><p>Em seus primeiros lançamentos, UNIX era um projeto de código aberto. Ele foi estudado, modificado e reescrito por muitos grupos de desenvolvedores que criaram uma grande família de sistemas operacionais <em>UNIX-Like</em>. A maioria dos sistemas operacionais modernos beberam, de alguma forma, da fonte do UNIX. Vale a pena, para qualquer interessado em tecnologia da informação, conhecer um pouco da história deste antigo e revolucionário projeto de software. Segue adiante, neste artigo, alguns detalhes sobre o contexto histórico e as características do UNIX.</p><h4>Os primeiros sistemas operacionais eram totalmente feitos em linguagens de montagem (Assembly)</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/580/1*sGfvXla7LdzQVD-abeN52w.jpeg" /><figcaption>Exemplo de código assembly para pdp-7 (fonte: <a href="https://github.com/DoctorWkt/pdp7-unix">https://github.com/DoctorWkt/pdp7-unix</a>)</figcaption></figure><p>Os primeiros sistemas operacionais eram, geralmente, desenvolvidos utilizando linguagens de montagem (geralmente chamadas pelo nome da família de linguagens que estas integram: “<em>Assembly</em>”). Estas linguagens de programação são, basicamente, notações legíveis para as instruções das suas respectivas arquiteturas de computadores. Na prática, uma instrução consiste de uma combinação de bits que, quando é disposta na unidade de controle do processador, induz uma determinada atividade no circuito eletrônico do computador. Cada arquitetura de computador tem seu próprio conjunto de instruções e, portanto, tem sua própria linguagem de montagem.</p><p>Quando as linguagens de montagem são utilizadas para construir programas muito complexos, fazem com que o desenvolvimento destes demandem demasiado tempo e esforço por parte dos programadores. Além do mais, há uma série de necessidades que elas, sozinhas, não são capazes de saciar. Um exemplo de necessidade que as linguagens de montagem não suprem é a da <strong>portabilidade</strong>. Cada arquitetura de computadores possui sua própria linguagem de montagem, com sua própria sintaxe. Se, por exemplo, houver a necessidade de elaborar um programa que funcione em várias arquiteturas diferentes, caso as linguagens de montagem das respectivas arquiteturas sejam utilizadas no desenvolvimento, este programa terá um código-fonte único para cada uma das arquiteturas, e os respectivos códigos serão diferentes em sintaxe e lógica. Outro exemplo de carência das linguagens de montagem está relacionada ao baixo nível de abstração destas, que dificulta a interpretação dos algoritmos e a identificação de erros lógicos em aplicações mais elaboradas, e isto se dá pela extrema complexidade que os códigos-fonte tomam conforme o programa é desenvolvido.</p><h4><strong>CTSS e MULTICS, as duas principais descendências do UNIX</strong></h4><p>Os computadores, muitas vezes, precisam suprir uma demanda de vários usuários utilizando-os simultaneamente e executando várias tarefas ao mesmo tempo. O que possibilita que múltiplos usuários e múltiplos processos sejam executados “simultaneamente” em um único processador é uma técnica chamada <em>time-sharing</em>.</p><p>Nos sistemas operacionais de <em>time-sharing</em>, a execução de instruções no processador é revezada entre os processos. Em uma situação onde há, por exemplo, dois processos sendo executados “ao mesmo tempo” pelo mesmo processador, o sistema operacional de <em>time-sharing</em> fica comutando a execução destes dois processos: ele escolhe um processo para ser executado e, depois de algumas frações de segundo, interrompe a execução deste processo para colocar outro processo em execução. Esta troca de processos é feita periodicamente. Ela é acionada por um hardware temporizador (que normalmente é um bloco funcional do <em>chipset</em>) através de uma <strong><em>IRQ</em> </strong>(acrônimo de <em>interrupt request</em>, do inglês, “requisição de interrupção”). Quando a <em>IRQ</em> é acionada pelo temporizador, o processador interrompe a execução do programa corrente para executar uma rotina do sistema operacional, que neste caso é a rotina de troca de processos. Esta troca abrupta de processos feita através de interrupções de hardware é denominada <strong>preempção</strong>. Sistemas operacionais de <em>time-sharing </em>possuem escalonamento preemptivo.</p><p>O primeiro sistema operacional a implementar <em>time-sharing</em> foi o <strong>CTSS</strong> (<em>compatible time-sharing system</em>), desenvolvido no MIT. O funcionamento do CTSS, equipando um computador IBM 7094, foi demonstrado pela primeira vez em 1961.</p><p>Após o desenvolvimento do CTSS, o MIT, em conjunto com as empresas <em>Bell</em> <em>Labs</em> e <em>General</em> <em>Electric</em>, tentou criar um sistema operacional mais ambicioso, o qual foi denominado <strong>MULTICS</strong> (<em>Multiplexed information and computing service</em>). Este sistema tinha por objetivo equipar um enorme computador capaz de suportar centenas de usuários conectados. Os idealizadores do projeto estavam interessados em criar um sistema operacional que fosse capaz de dar suporte a <strong>concessionárias de computação</strong>: empresas especializadas em distribuir, de forma compartilhada, o tempo de processamento de um único grande computador para vários usuários conectados remotamente.</p><p>O projeto MULTICS foi relativamente bem-sucedido. As empresas <em>Bell Labs</em> e <em>General Electric</em> abandonaram o projeto um suas fases iniciais, porém, com muito esforço dos desenvolvedores, o MIT conseguiu dar sucesso e comercializar o MULTICS. Mesmo assim, este sistema não cumpria com as expectativas de seus desenvolvedores, pois ainda que o fosse muito otimizado, os computadores tinham pouco poder de processamento para uma demanda muito alta.</p><h4><strong>O início do desenvolvimento do UNIX</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/310/1*foHOIkSl2Zx2ls5EAb85Hg.jpeg" /><figcaption>Ken Thompson (à esquerda) e Dennis Ritchie (à direita), os criadores do UNIX</figcaption></figure><p>Algum tempo depois, o cientista Ken Thompson, da<em> Bell Labs</em>, que havia trabalhado no desenvolvimento do MULTICS até a empresa abandonar o projeto, começou a escrever um novo sistema operacional baseado no MULTICS, utilizando um computador PDP-7. Este novo sistema era mais simples que o antigo MULTICS, e recebeu o nome <strong>UNIX</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*KI5lo1C9pq9qz2U6Kejz5w.jpeg" /><figcaption>Foto de um computador PDP-7, tirada em 2005 por Tore Sinding Bekkedal, na Noruega. (<a href="https://commons.wikimedia.org/wiki/File:Pdp7-oslo-2005.jpeg">https://commons.wikimedia.org/wiki/File:Pdp7-oslo-2005.jpeg</a>)</figcaption></figure><p>O projeto de Ken Thompson despertou interesse em seu colega de trabalho Dennis Ritchie, o qual passou a participar do desenvolvimento.</p><h4><strong>A criação da Linguagem C e a transcrição do UNIX.</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/318/1*PCGRjsKAtplEuFVoTdP0zQ.jpeg" /><figcaption>Capa do livro The C Programming Language, escrito pelos próprios criadores da linguagem</figcaption></figure><p>O código-fonte do UNIX, até então desenvolvido em linguagem de montagem, era demasiadamente reescrito, pois para não ficar obsoleto, precisava ser constantemente adaptado para novos modelos dos computadores PDP. A fim de sanar este problema, Ken Thompson reescreveu o UNIX em uma linguagem de programação que ele mesmo havia criado, chamada B. Esta tentativa de dar portabilidade ao sistema UNIX não foi bem sucedida por conta dos problemas e limitações que a linguagem B possuía.</p><p>Em uma nova tentativa de dar portabilidade ao UNIX, Dennis Ritchie desenvolveu, baseando-se na linguagem <strong>B</strong>, uma nova linguagem de programação chamada <strong>C</strong>. Esta tinha melhorias em relação a antecessora B.</p><p>Diferente de um algoritmo escrito em linguagem de montagem, um algoritmo escrito em C não requer tanto trabalho para ser adaptado de uma arquitetura de computadores a outra, já que a linguagem C não possui variações sintáticas ou lógicas para cada arquitetura. Além disso, a linguagem C é, sintaticamente e estruturalmente, muito mais abstrata do que as linguagens de montagem, tornando mais fácil o desenvolvimento e a interpretação dos algoritmos.</p><p>Após o desenvolvimento do primeiro compilador para a linguagem C, o UNIX foi em boa parte reescrito, da linguagem de montagem para C. A partir de então, o UNIX passou a ser um sistema portátil. Era possível fazê-lo funcionar em qualquer sistema computacional para o qual houvesse um compilador C, e isso foi um dos fatores preponderantes para que o UNIX se tornasse uma grande revolução no meio da computação.</p><h3><strong>As principais características do UNIX</strong></h3><h4>Diferenças de organização do MULTICS para o UNIX</h4><p>Uma das diferenças mais notáveis do MULTICS para o UNIX está no modo como estes são organizados. No MULTICS, as funcionalidades eram separadas em <strong>anéis de proteção</strong>, que eram basicamente camadas, cada uma delas com um nível de privilégio diferente sobre o controle do hardware. Apenas as funcionalidades do anel 0 eram executadas com privilégio total. Em todos os anéis “superiores”, as funcionalidades do sistema eram executadas com menos privilégios. O objetivo desta organização era fazer com que a menor quantidade possível de funcionalidades fossem executadas em modo supervisor. O sistema de arquivos, por exemplo, era executado no anel 1 ao invés do anel 0.</p><p>O UNIX, entretanto, possui uma tradicional organização monolítica. A maior parte das funcionalidades do sistema operacional, como o sistema de arquivos e os <em>drivers</em> de dispositivos, são executadas “dentro” do próprio <em>kernel</em>, em modo privilegiado.</p><h4><strong>Operação multiusuário</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/500/1*0x2nIDqCkvUmTk2el_8T7Q.png" /></figure><p>Assim como o MULTICS, o UNIX permite que vários usuários estejam utilizando simultaneamente um mesmo computador, sem que a atividade de um usuário interfira na do outro.</p><h4><strong>Processamento simultâneo</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/530/1*55KQwaOmllhPTYyLUX9GeQ.png" /></figure><p>O UNIX permite que o usuário execute várias tarefas simultaneamente, sem que precise interromper uma atividade para dar início a outra.</p><h4><strong>Desenho modular</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/688/1*4apLLhzMcB3trnGUNgIRDA.png" /></figure><p>O UNIX possui uma arquitetura modular. Ele é estruturado de modo a permitir que o usuário o adapte às suas necessidades removendo ou adicionando componentes sem comprometer o seu funcionamento. É graças à isso que os sistemas <em>UNIX-Like</em> são utilizados atualmente nas mais diversas aplicações, desde sistemas embarcados simples até grandes servidores de <em>internet</em>.</p><h4><strong>Portabilidade</strong></h4><p>Esta é, provavelmente, uma das características do UNIX que mais foi inovadora. O sistema UNIX pode ser adaptado para os mais diversos sistemas computacionais sem muito esforço, por conta da utilização da linguagem C.</p><h4><strong>Canalizações</strong></h4><p>Este recurso do sistema UNIX permite que os processos troquem informações através de <em>pipes</em>. As operações de leitura e escrita dos <em>pipes</em> são realizadas com a utilização de <em>file descriptors</em> e chamadas de sistema <em>read</em> e <em>write</em>.</p><h4><strong>Tudo é arquivo</strong></h4><p>No UNIX, todas as operações de entrada e saída do sistema são feitas com o uso de <em>file descriptors</em> e das chamadas de sistema <em>read</em> e <em>write</em>, as mesmas que são usadas para ler e escrever informações em arquivos.</p><h3><strong>Sistemas UNIX-Like</strong></h3><p>Em suas primeiras versões, o código-fonte do UNIX era distribuído livremente, permitindo que várias instituições contribuíssem com seu desenvolvimento. Entretanto, após alguns anos de desenvolvimento, o UNIX tornou-se comercial e deixou de ser <em>Open-Source.</em> A partir de então, foram desenvolvidos vários sistemas operacionais livres e similares ao UNIX, os quais são chamados de “sistemas <em>UNIX-Like</em>”, tais como o BSD e os sistemas <em>Linux-based</em>.</p><h4><strong>BSD</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*NTLchBgGRI_CZR1vmQwfEQ.png" /></figure><p>Ainda na época em que o Unix era um projeto de código aberto, o código fonte da versão 6 do software foi adquirido pela Universidade da Califórnia, em Berkeley. Com a ajuda dos financiamentos da ARPA (<em>Advanced Research Projects Agency</em>, do inglês, “Agência de Projetos de Pesquisas Avançadas”), do Departamento de Defesa dos Estados Unidos, foi desenvolvido dentro da Universidade de Berkeley o sistema operacional BSD (acrônimo de <em>Berkeley Software Distribution</em>), baseado no código fonte do UNIX. O código binário, assim como o código fonte do BSD, era distribuído livremente sob a licença BSD, uma licença pública muito permissiva.</p><p>Atualmente existem diversas variações do BSD, como o FreeBSD, OpenBSD e o NetBSD. Os atuais sistemas operacionais da empresa Apple, OS X (utilizado nos desktops e notebooks vendidos pela empresa) e IOS (utilizado nos Iphones), são parcialmente baseados no BSD.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/730/1*HbW4iUEPfIUhnFXsfHbTQw.png" /><figcaption>Screenshot do FreeBSD funcionando em uma maquina virtual</figcaption></figure><h4><strong>MINIX</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xF8VT5YFopg2HCFVeL9TyA.png" /><figcaption>Screenshot do Minix 3 com interface gráfica</figcaption></figure><p>O MINIX é um sistema operacional UNIX-Like. Foi desenvolvido pelo professor Andrew S. Tanenbaum para fins educacionais. O código fonte do sistema é utilizado como material de apoio do livro “Sistemas Operacionais - projeto e implementação”, escrito pelo próprio Andrew S. Tanenbaum. O nome MINIX é um acrônimo de “Mini UNIX”. Ele destina-se a computadores pessoais, especialmente os IBM PCs.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/430/1*k0uBMY1LUyBzLL4l5uMQTA.jpeg" /><figcaption>Capa da terceira edição do livro Sistemas Operacionais — Projeto e Implementação, de Andrew S. Tanenbaum</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/800/1*vgsrLaOQTXGujHl6Ys3rbg.jpeg" /><figcaption>Andrew S. Tanenbaum em uma apresentação na linux.conf.au, em 2007</figcaption></figure><p>O código fonte do MINIX é relativamente simples. Ele é classificado como um sistema de <strong>micro-<em>kernel </em></strong>por ter um <em>kernel</em> reduzido, que serve apenas para atividades mais básicas, como o escalonamento dos processos e o gerenciamento da memória principal. Todos os drivers e sistemas de arquivos são <em>deamons</em>, que são executados “acima do <em>kernel</em>”, como programas de usuário. Em contraste aos sistemas de micro-<em>kernel</em>, existem os sistemas de <em>kernel</em> monolítico, nos quais os drivers e sistemas de arquivos são executados como parte do <em>kernel</em>. Tanenbaum defende que sistemas de micro-<em>kernel</em> são mais robustos e seguros do que sistemas de <em>kernel</em> monolítico.</p><h4><strong>GNU/Linux</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/620/1*JLRrHsgu19keITiatBa0Yg.png" /><figcaption>À esquerda, o símbolo do projeto GNU. À direito, o pinguim Tux, símbolo do Linux.</figcaption></figure><p>Em 1989, o estudante finlandês Linus Torvalds resolveu criar seu próprio <em>kernel</em> de sistema operacional baseado no MINIX, o Linux. Inicialmente, Linus não tinha pretensão de fazer do Linux um grande projeto. Porém, o Linux despertou muito interesse na comunidade de usuários do MINIX (em especial aqueles que estavam insatisfeitos com a resistência de Tanenbaum a aprimoramentos no MINIX), pois o projeto de Linus não tinha fins educacionais e podia ser aprimorado sem preocupação com didática.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*-s_m9FL69LelbfZWmzmQSA.jpeg" /><figcaption>Linus Torvalds na LinuxCon Europe 2014, em Düsseldorf</figcaption></figure><p>Tanenbaum muitas vezes recebia, pela internet, pedidos de usuários para que novos recursos e aprimoramentos fossem adicionados ao MINIX. A fim de manter o código fonte do MINIX simples e fácil de compreender, Tanenbaum quase sempre recusava os pedidos, o que gerava uma certa insatisfação na comunidade de usuários de seu sistema.</p><p>Logo o Linux passou a ser desenvolvido por muitas pessoas do mundo todo, ganhando muitos recursos e tornando-se um poderoso software. Posteriormente, o <em>kernel</em> Linux tornou-se parte do projeto GNU, de Richard Stallman, cujo objetivo era criar um sistema operacional completo e totalmente livre, distribuído sob a licença GPL (que apesar de ser uma licença de software livre, tem suas restrições). A integração do <em>kernel</em> Linux ao projeto GNU deu origem ao sistema operacional GNU/Linux, o qual é base para uma grande família de sistemas operacionais. Entre eles, podemos citar as distribuições Debian, Slackware, Arch, Red Hat, Ubuntu, Fedora, entre muitas outras. O popular sistema operacional de dispositivos móveis Android, da Google, também é baseado no <em>kernel</em> Linux.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/700/1*jBV4Jzue0_f86KYQ-5Q1dQ.jpeg" /><figcaption>Richard Stallman na Espanha, no Parque Tecnológico Walqa, em Março de 2011</figcaption></figure><p>Em contraste ao MINIX, os sistemas operacionais baseados no Linux são classificados como de <em>kernel</em> monolítico, pois uma parte significativa de seus recursos estão concentrados no <em>kernel</em> Linux.</p><h4><strong>Referências</strong></h4><p>TANENBAUM, Andrew S. <strong>Sistemas Operacionais Modernos</strong>. 3ª Edição. São Paulo: PEARSON, novembro 2010.</p><p>L. STUART, Brian. <strong>Princípios de Sistemas Operacionais</strong>: Projetos e Aplicações. Tradução: All Tasks. São Paulo: Cengage Learning, 2011. ISBN 978–85–221–0733–9.</p><p>THOMAS, Rebeca; YETES, Jean. <strong>UNIX TOTAL.</strong> São Paulo: McGraw-Hill, 1989.</p><p>GROFF, James R.; WEINBERG, Paul N. <strong>Sistema Operacional Unix</strong>: Um guia conceitual. São Paulo: EBRAS, 1986.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2795d0fd564b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/programadores-ajudando-programadores/a-hist%C3%B3ria-do-unix-o-pai-dos-sistemas-operacionais-modernos-2795d0fd564b">UNIX, o pai dos sistemas operacionais modernos</a> was originally published in <a href="https://medium.com/programadores-ajudando-programadores">Programadores Ajudando Programadores</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Entendendo os circuitos dos flip-flops]]></title>
            <link>https://medium.com/@filipe.chagas/entendendo-os-circuitos-dos-flip-flops-6c6ee1d6bf47?source=rss-afd6aeaaa729------2</link>
            <guid isPermaLink="false">https://medium.com/p/6c6ee1d6bf47</guid>
            <category><![CDATA[digital]]></category>
            <category><![CDATA[engenharia]]></category>
            <category><![CDATA[eletrônica]]></category>
            <dc:creator><![CDATA[Filipe Chagas Ferraz]]></dc:creator>
            <pubDate>Mon, 10 Sep 2018 01:14:43 GMT</pubDate>
            <atom:updated>2020-06-28T08:37:24.962Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/777/1*JIv7JhjPm2RxejklRC0hxw.png" /><figcaption>Circuito lógico de um contador de 4 bits com flip-flops do tipo T</figcaption></figure><p><em>Flip-flops</em> são, basicamente, circuitos digitais de memória. Cada <em>flip-flop</em> corresponde a uma memória de 1 bit. <br>Existem diversos tipos de <em>flip-flops</em>, cada um deles com suas aplicações. Cada tipo de <em>flip-flop </em>possui um conjunto de propriedades para as quais devemos modelar um circuito. Isso significa que, para cada tipo de <em>flip-flop</em>, existe um circuito digital diferente dos circuitos dos demais tipos. Estes vários circuitos diferentes, entretanto, possuem semelhanças.</p><p>Analisaremos aqui 4 tipos de <em>flip-flops</em>: <em>SR</em>, <em>D</em>, <em>JK</em> e <em>T</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/860/1*KpbCCf066LjCGB5qUPGtSA.png" /><figcaption>Circuito lógico de um flip-flop JK</figcaption></figure><p>Observe, na imagem acima, o circuito lógico de um <em>flip-flop JK</em>. Confuso, não acha ? A primeira vista ele aparenta ser, realmente, bem complexo, mas se analisarmos parte por parte de sua anatomia, tudo ficará mais simples.</p><h3>Latch SR (set-reset)</h3><p>Tudo começa com um pequeno e simples circuito <em>latch set-reset</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*Jft4eFAnxTG77ETP9SPkQw.gif" /><figcaption>Simulação de um circuito lógico set-reset. (O botão de cima é a entrada set, o botão de baixo é a entrada reset, a lâmpada de cima é a saída Q e a lâmpada de baixo é a saída Q’)</figcaption></figure><p>Este pequeno circuito é a base de todos os<em> flip-flops</em>. Ele possui 2 entradas (chamadas <em>set</em> e <em>reset</em>) e 2 saídas (chamadas <strong><em>Q</em></strong> e <strong><em>Q’</em></strong>). Quando a entrada <em>set</em> (ou simplesmente <strong><em>S</em></strong>) passa do nível lógico 0 para o 1, o circuito “memoriza” o nível lógico 1 na saída <strong><em>Q</em></strong> e o nível lógico 0 na saída <strong><em>Q’</em></strong>. Da mesma forma, quando a entrada <em>reset</em> (ou simplesmente <strong><em>R</em></strong>) passa do nível lógico 0 para o 1, o circuito “memoriza” o nível lógico 1 na saída <strong><em>Q’</em></strong> e o nível lógico 0 na saída <strong><em>Q</em></strong>. Isso significa que, caso as saídas do circuito sejam <strong><em>Q = 1</em></strong> e <strong><em>Q’ = 0</em></strong>, elas permanecem nesse estado até que a entrada <strong><em>R</em></strong> passe do nível lógico 0 para o 1. Da mesma forma, caso as saídas do circuito sejam <strong><em>Q = 0</em></strong> e <strong><em>Q’ = 1</em></strong>, elas permanecem nesse estado até que a entrada <strong><em>S</em></strong> passe do nível lógico 0 para o 1.<br>Enquanto o nível lógico das duas entradas é 0, o estado das saídas <strong>Q</strong> e <strong>Q’</strong> não é alterado, até que alguma das duas entradas passe para o nível lógico 1.<br>Observe que as saídas <strong>Q</strong> e <strong>Q’</strong> sempre possuem níveis lógicos complementares: Se <strong><em>Q = 1</em></strong>, então <strong><em>Q’ = 0</em></strong>; Se <strong><em>Q = 0</em></strong>, então <strong><em>Q’ = 1</em></strong>.</p><p>Entretanto, caso ambas as entradas estejam em nível lógico 1, ocorrerá um erro lógico que fará com que o circuito não se comporte de acordo com esta regra.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*OAguO5REqpjK2PK_0YoMTA.gif" /><figcaption>Simulação de erro lógico em um circuito latch set-reset. (O botão esta ligado nas duas entradas. Alâmpada de cima é a saída Q e a lâmpada de baixo é a saída Q’)</figcaption></figure><p>Será abordada mais adiante uma solução para este problema, mas antes disso vamos continuar analisando os circuitos <em>set-reset</em>.</p><h3>Flip-flop SR (set-reset)</h3><p>Nas aplicações dos<em> flip-flops</em> é necessário que as mudanças de estado do circuito ocorram em sincronia com os pulsos de um <em>clock</em>.</p><p>A maneira mais simples de adicionar um <em>clock</em> a um circuito <em>set-reset</em> é substituir as portas <em>NOT</em> das entradas <strong><em>S</em></strong> e <strong><em>R</em></strong> por duas portas <em>NAND</em>. Cada uma dessas portas <em>NAND</em> deve ter duas entradas: Uma para a respectiva entrada (<strong><em>S</em></strong> ou <strong><em>R</em></strong>) do circuito, e outra para o <em>clock</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/480/1*KwNIqMrkXm7I7k2pimTKRQ.gif" /><figcaption>Circuito set-reset com clock. (O botão de cima é a entrada set, o botão de baixo é a entrada reset, a lâmpada de cima é a saída Q e a lâmpada de baixo é a saída Q’)</figcaption></figure><p>Este circuito tem um falha: O estado das saídas fica suscetível a mudanças enquanto o <em>clock</em> estiver em nível lógico 1, e não queremos isso. Queremos um circuito que só esteja suscetível a mudanças de estado nas saídas no exato momento em que o nível lógico do <em>clock</em> passa de 0 para 1 (momento este que chamaremos de “borda de subida”). Em outras palavras, as saídas <strong><em>Q</em></strong> e <strong><em>Q’</em></strong><em> </em>não podem mudar de estado em nenhum momento que não seja uma borda de subida do <em>clock</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/252/1*lJnLczRkwlQGapcaiceb3Q.png" /><figcaption>Gráfico que mostra o comportamento das entradas e saídas de um flip-flop SR. Os gráficos de Q e Q’ em vermelho são os graficos do comportamento ideal.</figcaption></figure><p>Para isso, é necessário fazer uma associação de dois circuitos <em>set-reset </em>com clock<em> </em>em uma configuração <em>master-slave</em>. As saídas <strong><em>Q</em></strong> e <strong><em>Q’</em></strong> do circuito <em>master</em> devem ser ligadas, respectivamente, nas entradas <strong><em>S</em></strong> e <strong><em>R</em></strong> do circuito <em>slave</em>. O <em>clock</em> deve ser invertido com uma porta <em>NOT</em> na entrada do circuito <em>master</em>, e no circuito <em>slave</em>, o <em>clock</em> deve entrar sem inversão ou com duas inversões seguidas.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*9CBecSYjszFjAZnAxcowkQ.gif" /><figcaption>Circuito set-reset master-slave (entradas e saídas indicadas)</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*iw05-UXE4bN9HaqaBQ5-OA.gif" /><figcaption>Circuito set-reset master-slave simplificado</figcaption></figure><p>Observe que, agora, as saídas do circuito só mudam de estado na borda de subida do <em>clock</em> (momento exato em que o nível lógico do <em>clock</em> passa de 0 para 1).</p><p>O sinal de <em>clock</em> que entra no circuito <em>master</em> é inverso ao sinal de <em>clock</em> que entra no circuito <em>slave</em>. O circuito <em>master</em> fica suscetível a mudanças de estado enquanto o nível lógico do <em>clock</em> é 0, e o circuito <em>slave</em> fica suscetível a mudanças de estado enquanto o nível lógico do <em>clock</em> é 1.</p><p>O circuito <em>master </em>funciona como uma espécie de filtro nessa configuração. As entradas do circuito <em>slave</em> só recebem os sinais obtidos das entradas do circuito <em>master</em> enquanto o <em>clock</em> esta em nível lógico 0, e a mudança de estado nas saídas do circuito <em>slave</em> só ocorrem quando o <em>clock</em> esta em nível lógico 1.</p><p>A grosso modo, enquanto o <em>clock</em> esta em nível lógico 0, os sinais de entrada do circuito são memorizados no circuito <em>master. N</em>o momento em que o nível lógico do clock passa de 0 para 1 (borda de subida), as saídas do circuito <em>slave</em> são atualizadas de acordo com o estado memorizado no circuito <em>master</em>. Após a borda de subida, enquanto o <em>clock</em> esta em nível lógico 1, nenhuma mudança de estado ocorre no circuito.</p><h3>Entradas assíncronas <em>preset</em> e <em>clear</em></h3><p>Já conseguimos modelar um circuito de <em>flip-flops SR</em> com duas entradas síncronas (<strong><em>S</em></strong> e <strong><em>R</em></strong>), mas, para os próximos tipos de <em>flip-flops</em>, além disso, precisamos de duas entradas assíncronas, as quais chamaremos de <em>preset</em> e <em>clear </em>(ou simplesmente <strong><em>PRE</em></strong> e <strong><em>CLR</em></strong>). Essas duas entradas têm funções semelhantes às entradas <strong><em>S</em></strong> e <strong><em>R</em></strong>. A diferença é que as entradas <strong><em>PRE</em></strong> e <strong><em>CLR</em></strong> podem mudar o estado das saídas do <em>flip-flop</em> a qualquer momento, independente do estado do <em>clock</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*w7q5SHq3diKp3cLt_IzQ5Q.gif" /><figcaption>Demonstração do funcionamento das entradas PRE e CLR em um flip-flop SR</figcaption></figure><p>Para adicionar as entradas <strong><em>PRE</em></strong> e <strong><em>CLR</em></strong> ao nosso <em>flip-flop</em>, precisaremos acrescentar uma entrada a cada porta <em>NAND</em><strong><em> </em></strong>do circuito. Feito isso, precisamos conectar as entradas <strong><em>PRE</em></strong> e <strong><em>CLR </em></strong>invertidas, cada uma, com uma porta <em>NOT</em>, às portas <em>NAND</em><strong><em> </em></strong>como é mostrado nas animações a seguir:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/550/1*hnFXvQ8IDMMO5HdqzY7f9A.gif" /><figcaption>Conectando as entradas PRE e CLR (invertidas, cada uma, com uma porta NOT), às portas NAND do circuito master</figcaption></figure><p>O modo como as entradas <strong><em>PRE </em></strong>e <strong><em>CLR</em></strong> são conectadas às portas <em>NAND</em> é o mesmo nos circuitos <em>master</em> e <em>slave:</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1020/1*s9TlN1s6nFaaSxUor0Svcw.gif" /><figcaption>Conectando as entradas PRE e CLR (invertidas, cada uma, com uma porta NOT), às portas NAND do circuito master e slave</figcaption></figure><h3>Flip-flops JK</h3><p>Para corrigir o problema de erro lógico nos <em>flip-flops SR</em> quando ambas as entradas estão em nível lógico 1, existem os <em>flip-flops JK</em>, que são semelhantes aos SR, com uma diferença: Quando ambas as entradas (<strong><em>J</em></strong> e <strong><em>K</em></strong>) estão em nível lógico 1, ao invés de ocorrer um erro lógico, as saídas <strong><em>Q</em></strong> e <strong><em>Q’</em></strong><em> </em>têm seus estados invertidos.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/874/1*tSbsJDMEUhYqP40zKRO6Rw.gif" /><figcaption>Demostração do funcionamento de um flip-flop JK</figcaption></figure><p>Este circuito pode ser modelado com base no circuito de <em>flip-flop SR</em> que fizemos anteriormente. Basta conectar a saída <strong>Q’</strong> do circuito à porta <em>NAND</em> da entrada <strong><em>S</em></strong> e a saída <strong>Q</strong> à porta <em>NAND</em> da entrada <strong><em>R</em></strong>. Podemos desconectar as entradas <strong><em>PRE</em></strong> e <strong><em>CLR</em></strong> dessas duas portas <em>NAND</em> para dar lugar as novas conexões.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1020/1*v0vCQGXYlLN9tLfa_OncJg.gif" /><figcaption>Demonstração da modelagem de um flip-flop JK a partir do circuito de um flip-flop SR. (ignorem essas legendas indicando as conexões das entradas CLR e PRE nas portas NAND, eu esqueci de tirá-las antes de fazer a captura de tela)</figcaption></figure><h3>Flip-flops T e D</h3><p>Os outros dois tipos de<em> flip-flop</em> são baseados nos <em>flip-flops JK</em>. Não precisamos nem modificar o circuito que já fizemos, basta acrescentar algumas coisas.</p><p>Os <em>flip-flops T</em> (<em>toggle</em>) possuem entradas<em> clock</em><strong><em>, T</em></strong>, <strong><em>PRE</em></strong>, <strong><em>CLR</em></strong>, e saídas <strong><em>Q</em></strong> e <strong><em>Q’</em></strong>. Estes são, basicamente, <em>flip-flops</em> nos quais o estado das saídas é alternado na borda de subida do <em>clock</em> quando a entrada <strong><em>T </em></strong>esta em nível lógico 1.</p><p>Para modelar um<em> flip-flop T</em>, basta unir as entradas <strong><em>J</em></strong> e <strong><em>K</em></strong> de um <em>flip-flop JK</em> e transformá-las em uma única entrada <strong>T</strong>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*0AwHQUqW7-vNa5IYWq_DCw.gif" /><figcaption>Modelagem de um flip-flop T a partir de um flip-flop JK</figcaption></figure><p>Os <em>flip-flops D</em> (<em>data</em>) possuem entradas <em>clock</em>, <strong><em>D</em></strong>, <strong><em>PRE</em></strong>, <strong><em>CLR</em></strong>, e saídas <strong><em>Q</em></strong> e <strong><em>Q’</em></strong>. Estes são, basicamente, <em>flip-flops</em> nos quais o estado da saída <strong><em>Q</em></strong> é igualado ao estado da entrada <strong><em>D</em></strong> nas bordas de subida do <em>clock</em>.</p><p>Para modelar um <em>flip-flop D</em>, basta conectar a entrada <strong><em>D</em></strong> à entrada <strong><em>J</em></strong> do <em>flip-flop JK</em> e a entrada <strong><em>D</em></strong>, negada com uma porta <em>NOT</em>, à entrada <strong><em>K </em></strong>do <em>flip-flop JK</em>.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/600/1*s3bJArqg4cKNJYDww9DPCw.gif" /><figcaption>Modelagem de um flip-flop D a partir de um flip-flop JK</figcaption></figure><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6c6ee1d6bf47" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>