Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algoritmos Quânticos para Problemas em Teoria de Grupo Computacional

Demerson Nunes Gonçalves

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

Neste trabalho apresentamos um novo algoritmo quântico eficiente para o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p \rtimes Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(\sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é \Omega(\sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m \rtimes Z_p, com m, N inteiros positivos e N fatorado de forma especial.

Related papers

Algoritmos quânticos para o problema do isomorfismo de grafos

Edinelço Dalcumune

O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.

•Jan 1, 2008•1 citation

Um algoritmo quântico para casos não abelianos de HSP

Abner Fontebom Bissolli Costa

Resumo: O problema do subgrupo oculto, denominado HSP (de Hidden Subgroup Problem), é um problema candidato à classe de problemas NP-intermediários. A versão de decisão de HSP, denominada dHSP (de decision Hidden Subgroup Problem), é o problema de promessa de decidir se o subgrupo oculto é o subgrupo trivial ou não. Apresentamos uma análise de um algoritmo quântico de multiplicação de coclasses para dHSP, exibindo casos de grupos não abelianos que geram um estado próximo do estado maximamente misto, quando o subgrupo oculto não é o subgrupo trivial, e, por outro lado, geram um estado puro quando o subgrupo oculto é o subgrupo trivial. Adicionalmente, investigamos a relação de dHSP com classes de complexidade de conhecimento zero, apresentando casos particulares deste problema que estão em NIPZK1, a classe de problemas que admitem provas não-interativas de conhecimento zero perfeito com completude perfeita.

•Jan 1, 2024•0 citations

O algoritmo polinomial de Shor para fatoração em um computador quântico

Mário Sansuke Maranhão Watanabe

Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas

•Jan 1, 2003•0 citations

Resolvendo sistemas de equações lineares com o algoritmo quântico HHL: um tutorial com os fundamentos físicos e matemáticos para estudantes de graduação

Lucas Queiroz Galvão, Anna Beatriz M. de Souza, Alexandre Santos +2 more

resumo A computação quântica possibilita a resolução eficiente de problemas complexos, superando métodos clássicos em diversas aplicações. Em 2009, Harrow, Hassidim e Lloyd propuseram um algoritmo para solução de sistemas lineares, demonstrando aceleração exponencial (em condições ideais) com complexidade p o l y ( log N ), em contraste com abordagens clássicas que, no caso geral, apresentam complexidade da ordem de O ( N 3 ), ainda que possam atingir O ( N ) em casos específicos com matrizes esparsas. Esse algoritmo tem potencial para avanços em aprendizado de máquina, equações diferenciais, regressão linear e ataques a criptossistemas. No entanto, sua estrutura é complexa e há poucos materiais detalhados disponíveis na literatura. Neste contexto, este artigo pretende apresentar um tutorial abordando os fundamentos físicos e matemáticos do algoritmo HHL, direcionado para estudantes de graduação, explicando sua construção teórica e implementação para a resolução de sistemas de equações lineares. Após a discussão dos conceitos matemáticos e físicos subjacentes, apresentamos exemplos numéricos ilustrando a evolução do circuito quântico. Por fim, analisamos sua complexidade, limitações e perspectivas futuras. Os exemplos abordados são comparados com suas simulações clássicas, permitindo uma avaliação operacional da performance do algoritmo.

arXiv:2509.16640•Revista Brasileira de Ensino de Física•Jan 1, 2025•2 citations

Computação quântica e teoria de computação

Alex B. Grilo

A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação.Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável.Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências.Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação.Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema.Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica.Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo.Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial.Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas.Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos.Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas.

•Apr 11, 2014•0 citations

Alguns Comentários sobre Transformadas Quânticas

Bernardo Lula, Bruno Albert, Francisco de Assis

Resumo-Uma descoberta notável ocorrida na área da teoria da informac ¸ão e computac ¸ão quântica foi a prova de existência de um algoritmo quântico para fatorac ¸ão de inteiros de nbits com complexidade O(n 2 log n log log n) operac ¸ões.Este algoritmo é exponencialmente mais eficiente que o melhor algoritmo clássico correspondente que exige O(exp(n 1/3 log 2/3 )) operac ¸ões.A razão para a eficiência do algoritmo quântico mencionado é a existência de um algoritmo para o cálculo da transformada de Fourier quântica (QFT) de complexidade O((log N ) 2 ) enquanto o melhor algoritmo clássico (FFT) tem complexidade O(N log N ) para uma instâncias de tamanho N (em geral N = 2 n ).Este artigo focaliza de modo tutorial a QFT e introduz as transformadas de Hartley quânticas definindo-as e verificando algumas de suas propriedades mais importantes.Palavras-Chave-Tranformada discreta de Fourier quântica, transformada discreta de Hartley quântica.

Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais•Jan 1, 2005•0 citations
Neste trabalho apresentamos um novo algoritmo quântico eficiente para o Problema do Subgrupo Oculto (PSO) sobre uma classe especial de grupos metacíclicos, Z_p \rtimes Z_q^s, com q | (p-1) e p/q= poli(log p), onde p, q são números primos ímpares distintos e s um inteiro positivo qualquer. Em um contexto mais geral, sem impor uma relação entre p e q obtemos um algoritmo quântico com complexidade de tempo 2^{O(\sqrt{log p})}. Em qualquer caso, esses resultados são melhores que qualquer algoritmo clássico para o mesmo fim, cuja complexidade é \Omega(\sqrt{p}). Apresentamos também, algoritmos quânticos para o PSO sobre grupos não abelianos de ordem 2^{n+1} que possuem subgrupos cíclicos de índice 2 e para certos produtos semidiretos de grupos Z_N^m \rtimes Z_p, com m, N inteiros positivos e N fatorado de forma especial.
O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.
Resumo: O problema do subgrupo oculto, denominado HSP (de Hidden Subgroup Problem), é um problema candidato à classe de problemas NP-intermediários. A versão de decisão de HSP, denominada dHSP (de decision Hidden Subgroup Problem), é o problema de promessa de decidir se o subgrupo oculto é o subgrupo trivial ou não. Apresentamos uma análise de um algoritmo quântico de multiplicação de coclasses para dHSP, exibindo casos de grupos não abelianos que geram um estado próximo do estado maximamente misto, quando o subgrupo oculto não é o subgrupo trivial, e, por outro lado, geram um estado puro quando o subgrupo oculto é o subgrupo trivial. Adicionalmente, investigamos a relação de dHSP com classes de complexidade de conhecimento zero, apresentando casos particulares deste problema que estão em NIPZK1, a classe de problemas que admitem provas não-interativas de conhecimento zero perfeito com completude perfeita.
Sistemas de criptografia largamente difundidos como o RSA fundamentam a sua eficiência na suposição de que, em termos práticos, é impossível fatorar números inteiros suficientemente grandes em uma escala de tempo aceitável. Mais precisamente, não existem, até o momento, algoritmos de fatoração em tempo polinomial que possam ser implementados nos atuais computadores. Dentre os algoritmos conhecidos, o mais eficiente requer um tempo computacional de ordem exponencial na quantidade de dígitos binários do número a ser fatorado. Em 1994, baseado nos trabalhos anteriores de Benioff, Bennett, Deutsch, Feynman e Simon, dentre outros, Peter Shor apresentou um algoritmo de fatoração que requer assintoticamente uma quantidade em ordem polinomial de passos em um computador quântico para fatorar um número inteiro de tamanho arbitrário. Esse algoritmo ao invés de abordar o problema de decompor tal número em dois fatores não triviais pelo método direto de divisões sucessivas, utiliza o problema equivalente de encontrar a ordem de um certo inteiro modulo o número fatorado, onde esse inteiro é escolhido aleatoriamente relativamente primo com o número fatorado. Shor faz uso de um algoritmo quântico para calcular essa ordem. A computação quântica revela um paradigma computacional bastante adverso da computação clássica. Enquanto esta última é realizada através de operações binárias determinísticas com base na lógica booleana clássica, a computação quântica fundamenta as suas operações nos postulados que descrevem o comportamento quântico da matéria. Portanto, é probabilística no seu modus operandi. Essa diferença entre os formalismos lógicos da computação clássica e da computação quântica é um reflexo direto da natureza dos sistemas físicos que são utilizados para implementar concretamente cada uma dessas computações. Esta dissertação apresenta o algoritmo de Shor para fatoração em um computador quântico. Na seqüência, introduzimos no capítulo 1 alguns conceitos básicos da computação clássica com o objetivo de criar um ambiente de idéias favorável à apresentação da computação quântica como uma extensão, tão natural quanto possível, do modelo clássico computacional. Assim, no capítulo 2, apresentamos as bases do formalismo matemático que modela a computação quântica, atendo-nos apenas aos aspectos conceituais que são, direta ou indiretamente, aplicados na descrição do algoritmo de Shor. Os capítulos 3 e 4 são dedicados à apresentação do algoritmo de fatoração de Shor, feita em duas partes. A primeira diz respeito a parte não quântica e aborda os aspectos algébricos do algoritmo. Também é demonstrado o teorema que assegura a viabilidade probabilística da solução desse problema. No capítulo 4, apresentamos a parte quântica do algoritmo de Shor. O ponto alto da dissertação é alcançado mostrando-se como encontrar a ordem de um inteiro módulo o número a ser fatorado relativamente primo com este, conciliando o algoritmo quântico com uma interpretação clássica de seus dados de saída, mediante o uso da expansão de um número racional em frações contínuas
resumo A computação quântica possibilita a resolução eficiente de problemas complexos, superando métodos clássicos em diversas aplicações. Em 2009, Harrow, Hassidim e Lloyd propuseram um algoritmo para solução de sistemas lineares, demonstrando aceleração exponencial (em condições ideais) com complexidade p o l y ( log N ), em contraste com abordagens clássicas que, no caso geral, apresentam complexidade da ordem de O ( N 3 ), ainda que possam atingir O ( N ) em casos específicos com matrizes esparsas. Esse algoritmo tem potencial para avanços em aprendizado de máquina, equações diferenciais, regressão linear e ataques a criptossistemas. No entanto, sua estrutura é complexa e há poucos materiais detalhados disponíveis na literatura. Neste contexto, este artigo pretende apresentar um tutorial abordando os fundamentos físicos e matemáticos do algoritmo HHL, direcionado para estudantes de graduação, explicando sua construção teórica e implementação para a resolução de sistemas de equações lineares. Após a discussão dos conceitos matemáticos e físicos subjacentes, apresentamos exemplos numéricos ilustrando a evolução do circuito quântico. Por fim, analisamos sua complexidade, limitações e perspectivas futuras. Os exemplos abordados são comparados com suas simulações clássicas, permitindo uma avaliação operacional da performance do algoritmo.
A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação.Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável.Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências.Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação.Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema.Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica.Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo.Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial.Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas.Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos.Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas.
Resumo-Uma descoberta notável ocorrida na área da teoria da informac ¸ão e computac ¸ão quântica foi a prova de existência de um algoritmo quântico para fatorac ¸ão de inteiros de nbits com complexidade O(n 2 log n log log n) operac ¸ões.Este algoritmo é exponencialmente mais eficiente que o melhor algoritmo clássico correspondente que exige O(exp(n 1/3 log 2/3 )) operac ¸ões.A razão para a eficiência do algoritmo quântico mencionado é a existência de um algoritmo para o cálculo da transformada de Fourier quântica (QFT) de complexidade O((log N ) 2 ) enquanto o melhor algoritmo clássico (FFT) tem complexidade O(N log N ) para uma instâncias de tamanho N (em geral N = 2 n ).Este artigo focaliza de modo tutorial a QFT e introduz as transformadas de Hartley quânticas definindo-as e verificando algumas de suas propriedades mais importantes.Palavras-Chave-Tranformada discreta de Fourier quântica, transformada discreta de Hartley quântica.