As contemporary quantum computers do not possess error correction, any calculation performed by these devices can be considered an involuntary approximation. To solve a problem on a quantum annealer, it has to be expressed as an instance of Quadratic Unconstrained Binary Optimization (QUBO). In this work, we thus study whether systematically approximating QUBO representations of the MAX-3SAT problem can improve the solution quality when solved on contemporary quantum hardware, compared to using exact, non-approximated QUBO representations. For a MAX-3SAT instance consisting of a 3SAT formula with n variables and m clauses, we propose a method of systematically creating approximate QUBO representations of dimension (n× n), which is significantly smaller than the QUBO matrices of any exact, non-approximated MAX-3SAT QUBO transformation. In an empirical evaluation, we demonstrate that using our QUBO approximations for solving MAX-3SAT problems on D-Wave's quantum annealer Advantage_System6.4 can yield better results than using state-of-the-art exact QUBO transformations. Furthermore, we demonstrate that using naive QUBO approximation methods, based on removing values from exact (n+m)×(n+m)-dimensional QUBO representations of MAX-3SAT instances, is ineffective.

Modular quantum computing architectures are a promising alternative to monolithic QPU (Quantum Processing Unit) designs for scaling up quantum devices. They refer to a set of interconnected QPUs or cores consisting of tightly coupled quantum bits that can communicate via quantum-coherent and classical links. In multi-core architectures, it is crucial to minimize the amount of communication between cores when executing an algorithm. Therefore, mapping a quantum circuit onto a modular architecture involves finding an optimal assignment of logical qubits (qubits in the quantum circuit) to different cores with the aim to minimize the number of expensive inter-core operations while adhering to given hardware constraints. In this paper, we propose for the first time a Quadratic Unconstrained Binary Optimization (QUBO) technique to encode the problem and the solution for both qubit allocation and inter-core communication costs in binary decision variables. To this end, the quantum circuit is split into slices, and qubit assignment is formulated as a graph partitioning problem for each circuit slice. The costly inter-core communication is reduced by penalizing inter-core qubit communications. The final solution is obtained by minimizing the overall cost across all circuit slices. To evaluate the effectiveness of our approach, we conduct a detailed analysis using a representative set of benchmarks having a high number of qubits on two different multi-core architectures. Our method showed promising results and performed exceptionally well with very dense and highly-parallelized circuits that require on average 0.78 inter-core communications per two-qubit gate.