Using a Simplified Quantum Counter to Implement Quantum Circuits Based on Grover’s Algorithm to Tackle the Exact Cover Problem

Abstract

In this paper, we use a simplified quantum counter to implement Grover’s algorithm-based quantum circuits to tackle the NP-hard exact cover problem (ECP). The ECP seeks a subcollection of sets such that every element is covered by exactly one set. Leveraging Grover’s algorithm, our quantum circuits achieve a quadratic speedup, querying the oracle O(N) times, compared to O(N) for classical methods, where N=2n is the total number of unstructured input instances and n is the number of input (quantum) bits. For the whole quantum circuit, the simplified quantum counter saves (4mb−4m)⌊π/4N/M⌋ quantum gates and reduces the quantum circuit depth by (2mb)⌊π/4N/M⌋ compared to Heidari et al.’s design, where b=⌊logn⌋+1 is the number of counting qubits used in a counter. Experimental results obtained using IBM Qiskit packages confirm the effectiveness of our quantum circuits.

Keywords

• exact cover problem
• Grover’s algorithm
• oracle
• quantum circuit
• quantum counter
• quantum search