约束二元优化旨在寻找一种最优分配方式，以在满足约束条件的同时最小化或最大化目标函数，这是包括交通、调度和经济等领域中具有代表性的NP难题。量子近似优化算法（QAOA）通过利用量子纠缠的并行性为解决此类问题提供了一种有前景的方法。然而，现有基于惩罚项或哈密顿量模拟的QAOA方法未能完全编码约束条件，导致成功率极低且搜索延迟较长。本文提出了一种名为Choco-Q的形式化通用框架，用于解决约束二元优化问题，该框架全面涵盖了所有约束条件，并在当前量子设备上表现出较高的可部署性。Choco-Q的主要创新在于将交换哈密顿量嵌入为驱动哈密顿量，从而形成一种更通用的编码公式，能够处理任意线性约束。利用交换哈密顿量的算术特性，我们提出了三种优化技术以压缩整体电路复杂度，包括哈密顿量序列化、等效分解和变量消除。序列化机制将原始哈密顿量转化为更小的部分，我们的分解方法仅需线性时间复杂度，实现了端到端加速。实验表明，与先前的QAOA设计相比，Choco-Q在成功找到最优解方面提升了超过235倍的算法性能，并实现了4.69倍的端到端加速。

Constrained binary optimization aims to find an optimal assignment to minimize or maximize the objective meanwhile satisfying the constraints, which is a representative NP problem in various domains, including transportation, scheduling, and economy. Quantum approximate optimization algorithms (QAOA) provide a promising methodology for solving this problem by exploiting the parallelism of quantum entanglement. However, existing QAOA approaches based on penalty-term or Hamiltonian simulation fail to thoroughly encode the constraints, leading to extremely low success rate and long searching latency. This paper proposes Choco-Q, a formal and universal framework for constrained binary optimization problems, which comprehensively covers all constraints and exhibits high deployability for current quantum devices. The main innovation of Choco-Q is to embed the commute Hamiltonian as the driver Hamiltonian, resulting in a much more general encoding formulation that can deal with arbitrary linear constraints. Leveraging the arithmetic features of commute Hamiltonian, we propose three optimization techniques to squeeze the overall circuit complexity, including Hamiltonian serialization, equivalent decomposition, and variable elimination. The serialization mechanism transforms the original Hamiltonian into smaller ones. Our decomposition methods only take linear time complexity, achieving end-to-end acceleration. Experiments demonstrate that Choco-Q shows more than 235$\times$ algorithmic improvement in successfully finding the optimal solution, and achieves 4.69$\times$ end-to-end acceleration, compared to prior QAOA designs.