  Quantum annealers offer an efficient way to compute high quality solutions of
NP-hard problems when expressed in a QUBO (quadratic unconstrained binary
optimization) or an Ising form. This is done by mapping a problem onto the
physical qubits and couplers of the quantum chip, from which a solution is read
after a process called quantum annealing. However, this process is subject to
multiple sources of biases, including poor calibration, leakage between
adjacent qubits, control biases, etc., which might negatively influence the
quality of the annealing results. In this work, we aim at mitigating the effect
of such biases for solving constrained optimization problems, by offering a
two-step method, and apply it to Graph Partitioning. In the first step, we
measure and reduce any biases that result from implementing the constraints of
the problem. In the second, we add the objective function to the resulting
bias-corrected implementation of the constraints, and send the problem to the
quantum annealer. We apply this concept to Graph Partitioning, an important
NP-hard problem, which asks to find a partition of the vertices of a graph that
is balanced (the constraint) and minimizes the cut size (the objective). We
first quantify the bias of the implementation of the constraint on the quantum
annealer, that is, we require, in an unbiased implementation, that any two
vertices have the same likelihood of being assigned to the same or to different
parts of the partition. We then propose an iterative method to correct any such
biases. We demonstrate that, after adding the objective, solving the resulting
bias-corrected Ising problem on the quantum annealer results in a higher
solution accuracy.
