Otimização combinatória e computação quântica: modelagem, implementação e resolução do Problema da Régua de Golomb

Neste artigo abordamos o Problema da Régua de Golomb, que consiste em determinar a menor régua com $n$ marcas de forma a que as distâncias entre suas marcas sejam todas diferentes. Este problema é extremamente combinatório e são conhecidas as soluções ótimas apenas para problemas de pequeno porte. Com o advento da computação quântica, abre-se uma oportunidade da obtenção de soluções ótimas para Réguas de Golomb com diversas marcas, que podem contribuir com soluções inovadoras para problemas importantes na física, astronomia, teoria de códigos, entre outras áreas. Este trabalho apresenta um modelo matemático para o Problema da Régua de Golomb de forma a permitir sua resolução por meio do Algoritmo de Grover em um Computador Quântico. É apresentado ainda uma variação de um modelo linear para o problema com um número de restrições menor do que em outros modelos presentes na literatura. O artigo apresenta também um passo a passo detalhado de como usar a computação quântica por meio do IBM Quantum Lab para resolver problemas de otimização combinatória, incluindo acesso ao código desenvolvido em Python e as bibliotecas utilizadas.