Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

Resumo Técnico: Comparação de Codificações de Qubit e Qudit para Problemas de Carregamento de Veículos Elétricos e Atribuição de Viagens

Enunciado do Problema
O artigo aborda o problema de otimização restrita de gerenciar uma frota de veículos elétricos (VEs). Isso envolve dois processos decisórios acoplados: agendar o carregamento bidirecional (ou unidirecional) de $N_{EV}$ veículos ao longo de um horizonte de tempo discreto $T$, e atribuir esses veículos a $R$ solicitações de viagem de clientes. O objetivo é minimizar os custos de carregamento enquanto satisfaz restrições operacionais rigorosas, incluindo limites do estado de carga (SOC) da bateria, sobreposições de viagens, limites de potência da rede e a exigência de que um veículo não pode carregar enquanto atende a uma viagem.

O desafio central investigado é como a escolha da codificação para as variáveis de atribuição de viagem afeta os requisitos de recursos e o comportamento de otimização de Algoritmos Quânticos Variacionais (VQAs), especificamente o Algoritmo Quântico Aproximado de Otimização (QAOA). Os autores comparam duas representações distintas:

1. Codificação Binária (Qubit): Utiliza uma variável binária ($r_{n,i} \in \{0,1\}$) para cada par VE-viagem. Isso requer restrições explícitas para garantir que cada viagem seja atendida por no máximo um VE e que viagens sobrepostas não sejam atribuídas ao mesmo veículo.
2. Codificação Inteira (Qudit): Utiliza uma variável inteira ($q_i \in \{0, \dots, N_{EV}\}$) por viagem, onde o valor especifica diretamente o VE atribuído (ou um estado de não atendido). Esta codificação satisfaz inerentemente a restrição "um VE por viagem", removendo a necessidade de restrições binárias explícitas na atribuição.

Metodologia
Os autores formulam o problema usando QAOA. Ambas as codificações utilizam variáveis qudit para os níveis de potência de carregamento ($l_{n,t}$), mas diferem na base computacional para atribuições de viagem.

• Construção do Hamiltoniano: As funções de custo clássicas e as restrições são promovidas a operadores diagonais na base computacional. Restrições (por exemplo, limites de SOC, sem carregamento durante viagens) são impostas por meio de termos de penalidade não lineares adicionados ao Hamiltoniano de custo.
• Simulação: O estudo emprega simulações exatas de vetores de estado para avaliar os algoritmos. Para imitar limitações de hardware realistas, os valores esperados da função de custo são estimados usando um número finito de disparos de medição ($M=256$) em vez de cálculo exato.
• Otimização: Um otimizador clássico (método de Powell) minimiza a função de custo variando os parâmetros do QAOA ($\gamma, \beta$). O estudo executa 10 instâncias aleatórias para cada classe de problema, com 10 execuções de otimização por instância, usando um orçamento fixo de 200 iterações internas do otimizador.
• Casos de Teste: Duas classes de problema são analisadas:
  • Carregamento bidirecional: 3 VEs, 2 passos de tempo, 2 viagens, 3 níveis de carregamento ($d=3$).
  • Carregamento unidirecional: 2 VEs, 3 passos de tempo, viagens variáveis ($R=2,3,4$), 2 níveis de carregamento ($d=2$).

Principais Contribuições e Resultados
O artigo fornece uma análise comparativa das duas codificações através de várias métricas:

1. Redução do Espaço de Hilbert: A codificação inteira (qudit) reduz exponencialmente a dimensão do espaço de Hilbert em comparação com a codificação binária (qubit). A razão de configurações é dada por $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. Para as instâncias testadas, isso resulta em uma redução do espaço de busca de dezenas de milhares para alguns milhares de estados.
2. Desempenho de Otimização:
   • Gap de Energia Médio: A codificação qudit alcança consistentemente um gap de energia médio comparável ou ligeiramente melhor que a codificação qubit.
   • Variância: Os resultados qudit exibem variância significativamente menor nos gaps de energia entre diferentes execuções.
   • Probabilidade de Sucesso: A fração de execuções que encontram o ótimo global e a fração de estados viáveis amostrados são geralmente maiores ou mais estáveis para a codificação qudit.
3. Tempo de Execução e Convergência:
   • Tempo de Execução da Simulação: Devido ao menor espaço de Hilbert, a codificação qudit requer tempos de execução de simulação substancialmente mais curtos (lineares na profundidade do circuito, mas com um coeficiente muito menor).
   • Comportamento da Profundidade de Camadas: À medida que a profundidade do QAOA ($L$) aumenta, o desempenho da codificação qubit degrada-se mais significativamente do que a codificação qudit. Os autores atribuem isso ao aumento do número de parâmetros variacionais, tornando a paisagem de otimização mais difícil de navegar dentro de um orçamento fixo de iterações. A codificação qudit é mais robusta à terminação prematura do otimizador clássico.
4. Paisagem de Custos: As paisagens de custo para a codificação qubit mostram uma escala de energia maior e frequências de oscilação mais altas devido à maior fração de estados inviáveis (que incorrem em altos custos de penalidade) em comparação com a codificação qudit.

Significância e Alegações
O artigo alega que codificações nativas de qudit oferecem uma rota prática para resolver problemas de agendamento inteiros e multivalorados em otimização quântica variacional. A principal significância reside em demonstrar que representar variáveis discretas multivaloradas diretamente via qudits, em vez de expandi-las em qubits binários, produz:

• Economia exponencial de recursos na dimensão do espaço de Hilbert.
• Redução da sobrecarga computacional em simulações clássicas (servindo como um proxy para complexidade representacional).
• Melhor robustez no processo de otimização, particularmente em regimes altamente restritos onde soluções viáveis são escassas.

Os autores observam que, embora o estudo utilize simulações de vetores de estado, a representação compacta sugere benefícios potenciais para implementações em hardware, reduzindo a sobrecarga do tratamento de restrições e do mapeamento de variáveis lógicas. Eles concluem que, para problemas de agendamento restritos, a codificação qudit é uma escolha superior que mantém ou melhora o desempenho de otimização enquanto reduz drasticamente os requisitos de recursos. O artigo sugere modestamente que trabalhos futuros devem testar essas tendências em instâncias maiores e em hardware quântico real para verificar se as vantagens persistem além da simulação.