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

Algorithms for solving pseudo-boolean optimization problems

Eduardo A.J. Anacleto

Published Jun 21, 2023• 0 citations
OpenAlex

Abstract

Investigamos os problemas de Otimização Pseudo-Booleana (PBO), Otimização Quadrática Binária Irrestrita (QUBO) e Programação Quadrática Booleana com Restrições de Limitantes Superiores Generalizados (BQP-GUB). Estes problemas pertencem 'a classe de complexidade computacional NP-difícil e têm sido estudados desde os anos 60. A busca por m'métodos para resolver esses problemas constitui um campo de pesquisa ativo, devido a situações reais que podem ser modeladas por meio deles. Em virtude de apelos práticos, pesquisadores têm mostrado grande interesse no desenvolvimento desses métodos. Com o intuito de contribuir de maneira significativa para esta área de pesquisa: (a) propomos um algoritmo exato para resolver os problemas PBO e QUBO; (b) projetamos um algoritmo de tempo polinomial para resolver classes de instâncias dos problemas PBO e QUBO; (c) desenvolvemos fórmulas para gerar limitantes para os valores de soluções ótimas para o problema QUBO; (d) criamos fórmulas para calcular rapidamente o valor da função objetivo do BQP-GUB; e (e) reformulamos problemas de otimização combinatória para a forma dos problemas QUBO e BQP-GUB.

Related papers

Otimização em computadores quânticos: formulação QUBO para o problema CMO

Nicolas M. de Oliveira

A computação quântica é um paradigma computacional que tem motivado o aparecimento de diversas pesquisas que visam apresentar soluções para problemas, atualmente, considerados difíceis. O surgimento de algoritmos quânticos que operam mais rápido que seus análogos clássicos tem feito com que corporações como Google, NASA e IBM invistam nesse paradigma. Por isso, intensificou-se a busca por formulações alternativas para problemas, visando resolvê-los em um ambiente computacional quântico. Entre essas formulações, estão os trabalhos que abordam a resolução de problemas na computação quântica a partir de formulações QUBO (Quadratic Unconstrained Binary Optimization), um problema NP-difícil cujo princípio consiste em minimizar uma função quadrática. O formato QUBO é comumente utilizado na literatura quando da solução quântica de problemas de otimização e diversos autores têm recorrido à esta caracterização devido à sua aplicabilidade em uma considerável gama de problemas. Dessa forma, representar um dado problema como um problema QUBO implica diretamente que podemos executá-lo em um ambiente computacional quântico (genérico ou de propósito específico). O problema CMO (Contact Map Overlap) é definido como um problema de otimização combinatória NPdifícil que consiste na medida de semelhança entre pares de proteínas com base em seus respectivos mapas de contato. Em bioinformática, o estudo de problemas que buscam por funções similares entre estruturas biológicas, especialmente de proteínas, é um campo de grande interesse. Com isso, este trabalho de pesquisa aborda o problema CMO na conjectura da resolução dos problemas de otimização em computadores quânticos através da formulação QUBO dos mesmos. Além de fornecermos uma formulação QUBO para o problema de proteína CMO, resultados experimentais foram obtidos com o auxílio da ferramenta qbsolv e validaram esta abordagem como uma alternativa aos métodos clássicos existentes.

•Feb 22, 2018•0 citations

Resolução de Problemas de Seleção de Características com Algoritmos Quânticos em Dados Financeiros Reais

Lucas Queiroz Galvão, Otto Menegasso Pires, Yan Alef Chagas +2 more

O setor financeiro enfrenta desafios significativos ao lidar com conjuntos de dados de alta dimensionalidade e um número limitado de amostras, dificultando a construção de modelos preditivos robustos. Técnicas tradicionais de aprendizado de máquina ajudam a mitigar esses problemas, mas a presença de características irrelevantes e redundantes aumenta a complexidade computacional. Este artigo apresenta a aplicação de algoritmos quânticos na seleção de características usando dados reais do setor financeiro, demonstrando que esses algoritmos podem melhorar a eficiência e a precisão dos modelos preditivos. A abordagem envolve a formulação do problema em termos de Otimização Binária Quadrática Irrestrita (QUBO), e sua solução é implementada em simuladores de um annealer quântico. Os experimentos mostram resultados promissores, que são analisados adotando-se a métrica do Critério de Informação de Akaike. Os resultados sugerem que os algoritmos quânticos variacionais têm grande potencial de aplicação se comparados a técnicas tradicionais de seleção de características.

VETOR - Revista de Ciências Exatas e Engenharias•Dec 18, 2024•1 citation

AN IMPROVED EXACT METHOD FOR THE UBQP

Daniel Fleischman

A Programação Quadrática Binária Irrestrita (UBQP) é amplamente\nestudada. Trata-se de uma ferramenta de modelagem poderosa, mas\notimizar de um problema NP-difícil. Neste trabalho uma nova abordagem\né apresentada, que pode ser usada para construir um algoritmo exato.\nAlém disso, a ideia básica que fundamenta o trabalho pode ser usado em\num espectro ainda mais amplo de problemas. O algoritmo exato derivado\ndo novo método é altamente paralelizável, o que é uma característica\ndesejável nos dias de hoje em que cloud computing já é uma realidade. Para\ninstâncias razoavelmente grandes do UBQP, o novo método pode paralelizar\na centenas, ou até milhares, de núcleos com facilidade, com um aumento\nde desempenho quase linear.

•Aug 4, 2010•1 citation

Avaliação Rápida em Problemas de Otimização Binária

Eduardo A.J. Anacleto, Cláudio N. Meneses

Neste trabalho, apresentamos um resultado original que possibilita acelerar o processo de resolucao do problema de Programacao Quadratica Binaria Irrestrita. A partir desse resultado, desenvolvemos um algoritmo e realizamos experimentos computacionais com instâncias disponiveis na literatura do problema.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Feb 14, 2018•0 citations

Decomposições Lagrangeanas para o problema de programação quadrática binária irrestrita

Geraldo Regis Mauri, Luiz Antônio Nogueira Lorena

O Problema de Programação Quadrática Binária Irrestrita - PQ é um dos problemas clássicos na área de otimização não-linear cujo objetivo é otimizar uma função quadrática através da escolha de valores binários apropriados para as variáveis de decisão. Este trabalho propõe novas alternativas de decomposição Lagrangeana para obtenção de limitantes para o PQ. Os métodos propostos tratam uma versão linear inteira mista (PQL) do PQ que tem restrições representadas através de um grafo. Esse grafo é particionado em clusters de vértices formando um problema dual cuja solução é dada por um algoritmo de subgradiente. A cada iteração desse método, os subproblemas formados pelos subgrafos gerados são resolvidos pelo CPLEX. Experimentos computacionais tratam um conjunto de dados formado por diversas instâncias de difícil solução e diferentes características. Os resultados mostram a eficiência dos métodos propostos em relação a métodos tradicionais de relaxação Lagrangeana e outros métodos encontrados na literatura.

Pesquisa Operacional•Apr 1, 2009•2 citations

Computação quântica sem colapso e problemas de conhecimento zero

Henrique Hepp

Resumo: A classe de problemas para os quais existem algoritmos quânticos eficientes é denotada por BQP (Bounded-error Quantum Polynomial). Uma abordagem comum em teoria da computação para a compreensão dos limites de uma classe de complexidade é esclarecer relações desta com outras subclasses e superclasses próximas. Uma superclasse de BQP que tem sido foco de pesquisa recentemente é a classe naCQP (non-adaptive Collapse-free Quantum Polynomial Time), também conhecida como PDQP (Product Dynamical Quantum Polynomial time), introduzida por Aaronson et al. (2016), a qual corresponde a problemas que podem ser resolvidos eficientemente por um algoritmo quântico em um modelo hipotético de computação em que é possível realizar medições sem provocar o colapso do estado quântico. Provas interativas de conhecimento zero têm recebido muita atenção nas últimas décadas, em virtude de suas aplicações importantes em segurança de informação. A classe dos problemas que admitem provas interativas de conhecimento zero estatístico na computação clássica é a classe SZK (Statistical Zero Knowledge). Embora a relação entre BQP e SZK ainda seja desconhecida, Aaronson et al. (2016) mostraram que SZK está contida em naCQP. Uma das abordagens para investigação de separações entre classes é o estudo de suas relações relativas a um oráculo. Aaronson et al. (2016) mostraram que existe um oráculo A para o qual NPA ^ naCQPA. Nós provamos que existe um oráculo A para o qual PA = BQPa = SZKA = naCQPA ã (UP n coUP)A = EXPA, onde UP (Unambiguous Polynomial time) é uma subclasse importante de NP. Ainda, mostramos que, relativo a um oráculo A escolhido uniformemente de modo aleatório, temos (UP n coUP)A ^ naCQPA com probabilidade 1. Nossos resultados ampliam resultados de Bennett et al. (1997), Fortnow e Rogers (1999), Tamon e Yamakami (2001) e Aaronson et al. (2016). A classe SZK possui muitas subclasses notáveis, como NISZK e NIPZKi. A classe NISZK é associada a sistemas de prova com somente um envio de mensagem do provador para o verificador. Para NIPZK1, subclasse de NISZK, ainda é requirido conhecimento zero perfeito e que as instâncias positivas do problema sejam aceitas pelo verificador com probabilidade igual a 1. Mostramos um problema completo para NIPZK1 e também que uma restrição não trivial do problema de subgrupo oculto está em NIPZK1. Além disso, mostramos uma restrição não trivial de um problema completo para NISZK que está em BQP.

•Jan 1, 2025•0 citations
Investigamos os problemas de Otimização Pseudo-Booleana (PBO), Otimização Quadrática Binária Irrestrita (QUBO) e Programação Quadrática Booleana com Restrições de Limitantes Superiores Generalizados (BQP-GUB). Estes problemas pertencem 'a classe de complexidade computacional NP-difícil e têm sido estudados desde os anos 60. A busca por m'métodos para resolver esses problemas constitui um campo de pesquisa ativo, devido a situações reais que podem ser modeladas por meio deles. Em virtude de apelos práticos, pesquisadores têm mostrado grande interesse no desenvolvimento desses métodos. Com o intuito de contribuir de maneira significativa para esta área de pesquisa: (a) propomos um algoritmo exato para resolver os problemas PBO e QUBO; (b) projetamos um algoritmo de tempo polinomial para resolver classes de instâncias dos problemas PBO e QUBO; (c) desenvolvemos fórmulas para gerar limitantes para os valores de soluções ótimas para o problema QUBO; (d) criamos fórmulas para calcular rapidamente o valor da função objetivo do BQP-GUB; e (e) reformulamos problemas de otimização combinatória para a forma dos problemas QUBO e BQP-GUB.
A computação quântica é um paradigma computacional que tem motivado o aparecimento de diversas pesquisas que visam apresentar soluções para problemas, atualmente, considerados difíceis. O surgimento de algoritmos quânticos que operam mais rápido que seus análogos clássicos tem feito com que corporações como Google, NASA e IBM invistam nesse paradigma. Por isso, intensificou-se a busca por formulações alternativas para problemas, visando resolvê-los em um ambiente computacional quântico. Entre essas formulações, estão os trabalhos que abordam a resolução de problemas na computação quântica a partir de formulações QUBO (Quadratic Unconstrained Binary Optimization), um problema NP-difícil cujo princípio consiste em minimizar uma função quadrática. O formato QUBO é comumente utilizado na literatura quando da solução quântica de problemas de otimização e diversos autores têm recorrido à esta caracterização devido à sua aplicabilidade em uma considerável gama de problemas. Dessa forma, representar um dado problema como um problema QUBO implica diretamente que podemos executá-lo em um ambiente computacional quântico (genérico ou de propósito específico). O problema CMO (Contact Map Overlap) é definido como um problema de otimização combinatória NPdifícil que consiste na medida de semelhança entre pares de proteínas com base em seus respectivos mapas de contato. Em bioinformática, o estudo de problemas que buscam por funções similares entre estruturas biológicas, especialmente de proteínas, é um campo de grande interesse. Com isso, este trabalho de pesquisa aborda o problema CMO na conjectura da resolução dos problemas de otimização em computadores quânticos através da formulação QUBO dos mesmos. Além de fornecermos uma formulação QUBO para o problema de proteína CMO, resultados experimentais foram obtidos com o auxílio da ferramenta qbsolv e validaram esta abordagem como uma alternativa aos métodos clássicos existentes.
O setor financeiro enfrenta desafios significativos ao lidar com conjuntos de dados de alta dimensionalidade e um número limitado de amostras, dificultando a construção de modelos preditivos robustos. Técnicas tradicionais de aprendizado de máquina ajudam a mitigar esses problemas, mas a presença de características irrelevantes e redundantes aumenta a complexidade computacional. Este artigo apresenta a aplicação de algoritmos quânticos na seleção de características usando dados reais do setor financeiro, demonstrando que esses algoritmos podem melhorar a eficiência e a precisão dos modelos preditivos. A abordagem envolve a formulação do problema em termos de Otimização Binária Quadrática Irrestrita (QUBO), e sua solução é implementada em simuladores de um annealer quântico. Os experimentos mostram resultados promissores, que são analisados adotando-se a métrica do Critério de Informação de Akaike. Os resultados sugerem que os algoritmos quânticos variacionais têm grande potencial de aplicação se comparados a técnicas tradicionais de seleção de características.
A Programação Quadrática Binária Irrestrita (UBQP) é amplamente\nestudada. Trata-se de uma ferramenta de modelagem poderosa, mas\notimizar de um problema NP-difícil. Neste trabalho uma nova abordagem\né apresentada, que pode ser usada para construir um algoritmo exato.\nAlém disso, a ideia básica que fundamenta o trabalho pode ser usado em\num espectro ainda mais amplo de problemas. O algoritmo exato derivado\ndo novo método é altamente paralelizável, o que é uma característica\ndesejável nos dias de hoje em que cloud computing já é uma realidade. Para\ninstâncias razoavelmente grandes do UBQP, o novo método pode paralelizar\na centenas, ou até milhares, de núcleos com facilidade, com um aumento\nde desempenho quase linear.
O Problema de Programação Quadrática Binária Irrestrita - PQ é um dos problemas clássicos na área de otimização não-linear cujo objetivo é otimizar uma função quadrática através da escolha de valores binários apropriados para as variáveis de decisão. Este trabalho propõe novas alternativas de decomposição Lagrangeana para obtenção de limitantes para o PQ. Os métodos propostos tratam uma versão linear inteira mista (PQL) do PQ que tem restrições representadas através de um grafo. Esse grafo é particionado em clusters de vértices formando um problema dual cuja solução é dada por um algoritmo de subgradiente. A cada iteração desse método, os subproblemas formados pelos subgrafos gerados são resolvidos pelo CPLEX. Experimentos computacionais tratam um conjunto de dados formado por diversas instâncias de difícil solução e diferentes características. Os resultados mostram a eficiência dos métodos propostos em relação a métodos tradicionais de relaxação Lagrangeana e outros métodos encontrados na literatura.
Resumo: A classe de problemas para os quais existem algoritmos quânticos eficientes é denotada por BQP (Bounded-error Quantum Polynomial). Uma abordagem comum em teoria da computação para a compreensão dos limites de uma classe de complexidade é esclarecer relações desta com outras subclasses e superclasses próximas. Uma superclasse de BQP que tem sido foco de pesquisa recentemente é a classe naCQP (non-adaptive Collapse-free Quantum Polynomial Time), também conhecida como PDQP (Product Dynamical Quantum Polynomial time), introduzida por Aaronson et al. (2016), a qual corresponde a problemas que podem ser resolvidos eficientemente por um algoritmo quântico em um modelo hipotético de computação em que é possível realizar medições sem provocar o colapso do estado quântico. Provas interativas de conhecimento zero têm recebido muita atenção nas últimas décadas, em virtude de suas aplicações importantes em segurança de informação. A classe dos problemas que admitem provas interativas de conhecimento zero estatístico na computação clássica é a classe SZK (Statistical Zero Knowledge). Embora a relação entre BQP e SZK ainda seja desconhecida, Aaronson et al. (2016) mostraram que SZK está contida em naCQP. Uma das abordagens para investigação de separações entre classes é o estudo de suas relações relativas a um oráculo. Aaronson et al. (2016) mostraram que existe um oráculo A para o qual NPA ^ naCQPA. Nós provamos que existe um oráculo A para o qual PA = BQPa = SZKA = naCQPA ã (UP n coUP)A = EXPA, onde UP (Unambiguous Polynomial time) é uma subclasse importante de NP. Ainda, mostramos que, relativo a um oráculo A escolhido uniformemente de modo aleatório, temos (UP n coUP)A ^ naCQPA com probabilidade 1. Nossos resultados ampliam resultados de Bennett et al. (1997), Fortnow e Rogers (1999), Tamon e Yamakami (2001) e Aaronson et al. (2016). A classe SZK possui muitas subclasses notáveis, como NISZK e NIPZKi. A classe NISZK é associada a sistemas de prova com somente um envio de mensagem do provador para o verificador. Para NIPZK1, subclasse de NISZK, ainda é requirido conhecimento zero perfeito e que as instâncias positivas do problema sejam aceitas pelo verificador com probabilidade igual a 1. Mostramos um problema completo para NIPZK1 e também que uma restrição não trivial do problema de subgrupo oculto está em NIPZK1. Além disso, mostramos uma restrição não trivial de um problema completo para NISZK que está em BQP.