A computação quântica é amplamente discutida por seu potencial de resolver problemas desafiadores de otimização de forma muito mais rápida. No entanto, os tamanhos dos problemas do setor aéreo atualmente excedem as capacidades do hardware quântico existente. Preparar-se para hardware quântico maior requer desenvolver e avaliar formulações de problemas mais adequadas para implementação quântica. Neste estudo, usamos o problema de emparelhamento de tripulação da aviação como um caso de uso para avaliar diferentes formulações de problemas: um modelo de particionamento de conjuntos e duas formulações compactas, um problema de atribuição de fluxo restrito e um problema de satisfatibilidade (SAT). Para a avaliação clássica, resolvemos essas formulações usando programação inteira mista e solucionadores de SAT. Para a avaliação quântica, traduzimos as formulações em otimização binária quadrática não restrita e formulações de Ising. Nossa avaliação mostra que as formulações de problemas levam a diferentes propriedades clássicas e quânticas. Entre as formulações consideradas, a formulação SAT se destaca como a candidata mais promissora para implementação futura em hardware quântico, com a menor participação de elementos não nulos e maior intervalo espectral, apesar de sua maior relação de coeficientes de termos lineares.
Stoebke et al. (Qui,) estudaram essa questão.