  A combinatorial optimization problem is to find an optimal solution under the
constraints. This is one of the potential applications for quantum computers.
Quantum Random Access Optimization (QRAO) is the quantum optimization algorithm
that encodes multiple classical variables into a single qubit to construct a
quantum Hamiltonian, thereby reducing the number of qubits required. The ground
energy of the QRAO Hamiltonian provides a lower bound on the original problem's
optimal value before encoding. This property allows the QRAO Hamiltonian to be
used as a relaxation of the original problem, and it is thus referred to as a
quantum relaxed Hamiltonian. In the Branch-and-Bound method, solving the
relaxation problem plays a significant role. In this study, we developed
Quantum Relaxation based Branch-and-Bound (QR-BnB), a method incorporating
quantum relaxation into the Branch-and-Bound framework. We solved the MaxCut
Problem and the Travelling Salesman Problem in our experiments. In all
instances in this study, we obtained the optimal solution whenever we
successfully computed the exact lower bound through quantum relaxation.
Internal strategies, such as relaxation methods and variable selection,
influence the convergence of the Branch-and-Bound. Thus, we have further
developed the internal strategies for QR-BnB and examined how these strategies
influence its convergence. We show that our variable selection strategy via the
expectation value of the Pauli operators gives better convergence than the
naive random choice. QRAO deals with only unconstrained optimization problems,
but QR-BnB can handle constraints more flexibly because of the Branch-and-Bound
processes on the classical computing part. We demonstrate that in our
experiments with the Travelling Salesman Problem, the convergence of QR-BnB
became more than three times faster by using the information in the
constraints.
