Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Zatesko, Leandro Miranda | - |
Autor(es): dc.contributor | Zatesko, Leandro Miranda | - |
Autor(es): dc.contributor | Groshaus, Marina Esther | - |
Autor(es): dc.contributor | Silva, Murilo Vicente Gonçalves da | - |
Autor(es): dc.creator | Dias, Matheus Giovanni | - |
Data de aceite: dc.date.accessioned | 2025-08-29T11:50:07Z | - |
Data de disponibilização: dc.date.available | 2025-08-29T11:50:07Z | - |
Data de envio: dc.date.issued | 2024-01-28 | - |
Data de envio: dc.date.issued | 2024-01-28 | - |
Data de envio: dc.date.issued | 2022-09-14 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/33230 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1084117 | - |
Descrição: dc.description | Determining the cardinality of the maximum clique on a simple graph is a NP-hard problem with several applications of interest. The best know classical algorithm for this problem has 𝒪(3𝑛/3) time complexity. Classical computing uses phenomena from classical physics to model, store and process information. Consequently, the entire model of classical computing is bounded superiorly by the limits of classical physics. As an alternative, Quantum Computing has been developed to take advantage of quantum phenomena and provide the constructions of circuits capable of performing certain computations more efficiently. In this paper, two quantum solutions to the maximum clique problem will be proposed and analyzed, based on the Grover Quantum Search algorithms and the Quantum Minimal Search Algorithm, comparing their respective time complexities with the best known classical solution. | - |
Descrição: dc.description | Determinar a cardinalidade da clique máxima em um grafo simples é um problema NP-difícil com diversas aplicações de interesse. O melhor algoritmo clássico conhecido para este problema tem complexidade de tempo 𝒪(3𝑛/3). A computação clássica utiliza fenômenos da física clássica para modelar, armazenar e processar a informação. Consequentemente, todo o modelo de computação clássica é limitado superiormente pelos limites da física clássica. Como alternativa, a Computação Quântica foi desenvolvida para aproveitar os fenômenos quânticos e proporcionar a construção de circuitos capazes de realizar certas computações de forma mais eficiente. Neste trabalho serão propostas e analisadas duas soluções quânticas para o problema da clique máxima, baseadas nos algoritmos de Busca Quântica de Grover e no Algoritmo Quântico de Busca do Mínimo, comparando suas respectivas complexidades de tempo com a melhor solução clássica conhecida. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Curitiba | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Engenharia de Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Direitos: dc.rights | http://creativecommons.org/licenses/by/4.0/ | - |
Palavras-chave: dc.subject | Computação quântica | - |
Palavras-chave: dc.subject | Algorítmos computacionais | - |
Palavras-chave: dc.subject | Algoritmos em grafos | - |
Palavras-chave: dc.subject | Complexidade computacional | - |
Palavras-chave: dc.subject | Quantum computing | - |
Palavras-chave: dc.subject | Computer algorithms | - |
Palavras-chave: dc.subject | Graph algorithms | - |
Palavras-chave: dc.subject | Computational complexity | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Algoritmos quânticos e o problema da clique máxima em grafos | - |
Título: dc.title | Quantum algorithms and the maximum clique problem in graphs | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: