911³Ô¹Ï

Synopsis

Most quantum hardware natively operates on binary variables with at most pairwise interactions. Combinatorial problems of practical interest, however, typically involve higher-arity discrete variables and higher-order interactions, and their reduction to Quadratic Unconstrained Binary Optimization (QUBO) form can inflate qubit count, introduce invalid states, or require quadratization that compounds both. Because quantum dynamics explore full Hilbert spaces regardless of which basis states correspond to valid configurations, encoding choice directly governs hardware performance within an optimization context. In this talk, I will present two qubit- and gate-efficient encodings that address this trade-off. The first, the approximate-binary encoding of pairwise-decomposable cost function networks, represents a $D$-choice discrete variable with $\lceil \log_2 D \rceil$ qubits while preserving the interaction order of the original problem; biases and couplings are obtained by rapidly solving a set of over-determined weighted least-squares systems on GPUs, with heuristics that concentrate residual approximation error at the high-energy end of solution landscapes. The second, a logarithmic Higher-Order Unconstrained Binary Optimization (HUBO) encoding for label-symmetric, pairwise-decomposable graph partitioning problems with label-cardinality minimization objectives---encompassing such problems as minimum graph coloring, minimum $k$-cut, and community detection---uses $\lceil \log_2 D \rceil$ bits per vertex and introduces a lexicographic penalty hierarchy that we prove is sufficient to enforce partition-count minimization, extending treatment of the decision variants of these problems to their optimization variants. Benchmarking the approximate-binary encoding across ${\sim}6{,}000$ realistic protein design problems on the D-Wave quantum annealer, we observe roughly a ten-fold improvement in the Time-to-Solution scaling exponent relative to one-hot encoding, resulting in performance on par with an adaptive simulated annealing protocol engineered specifically for protein design. Benchmarking the logarithmic encoding on $300$ random graph-coloring instances, we observe up to 2.5 orders of magnitude improvement in Time-to-Solution at only thirty vertices, despite post-quadratization physical-qubit counts matching the one-hot baseline. We find this advantage due to reduced embedding chain-length variance, and analysis suggests that advantage may widen on gate-based hardware where quadratization is unnecessary. Together, these results demonstrate that careful encoding design can extract substantial performance from current-generation quantum hardware on realistic combinatorial problems involving higher-arity variables.