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

Jehn-Ruey Jiang () and Yu-Jie Wang
Additional contact information
Jehn-Ruey Jiang: Department of Computer Science and Information Engineering, National Central University, Taoyuan 320317, Taiwan
Yu-Jie Wang: Department of Computer Science and Information Engineering, National Central University, Taoyuan 320317, Taiwan

Mathematics, 2024, vol. 13, issue 1, 1-31

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 = 2 n 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 ( 4 m b − 4 m ) ⌊ π / 4 N / M ⌋ quantum gates and reduces the quantum circuit depth by ( 2 m b ) ⌊ π / 4 N / M ⌋ compared to Heidari et al.’s design, where b = ⌊ log n ⌋ + 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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/1/90/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/1/90/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2024:i:1:p:90-:d:1555783

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().