Solving Segment Display Problems Using Quantum Grover's Search Algorithm
Preprint
Abstract
This paper introduces a new Boolean-based methodology for constructing Segment Display Problems (SDPs) in the quantum domain and solving them using Grover's quantum search algorithm. In the classical domain, the SDPs are typically solved using various techniques, such as human deduction, heuristic search, and methods for solving Boolean satisfiability (SAT) and constraint satisfaction problems (CSPs) that are based on different problem design models. In this paper, our newly introduced methodology proposes a quantum-based approach for solving such SDPs, by building their quantum oracle using binary reversible circuits and our previously proposed step-decreasing structures shaped operators (Stesso). To demonstrate the usability of this proposed method, we experimentally solve an SDP instance of the matchstick problem using Grover's algorithm with a noisy simulated quantum computer implemented in Qiskit.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- A concept of controlling Grover diffusion operator: a new approach to solve arbitrary Boolean-based problemsScientific Reports, 2024
- Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyondPhysical Review A, 2022
- A comprehensive study and analysis on SAT-solvers: advances, usages and achievementsArtificial Intelligence Review, 2018
- Solving a Binary PuzzleMathematics in Computer Science, 2017
- Fast escape of a quantum walker from an integrated photonic mazeNature Communications, 2016
- An overview of parallel SAT solvingConstraints, 2012
- Logical Cryptanalysis as a SAT ProblemJournal of Automated Reasoning, 2000
- Constraint satisfaction problems: Algorithms and applicationsEuropean Journal of Operational Research, 1999
- A generic arc-consistency algorithm and its specializationsArtificial Intelligence, 1992
- Predicting the relative difficulty of verbal arithmetic problemsEducational Studies in Mathematics, 1972