Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International journal of unconventional computing

Solving Minimum Hitting Set Problem and Generalized Exact Cover Problem with Light Based Devices.

Masud Hasan, S. M. Shabab Hossain, Mahmudur Rahman, M. Sohel Rahman

Published Jan 1, 2011• 1 citation
OpenAlex

Related papers

Solving a Generalized Version of the Exact Cover Problem with a Light-Based Device

S. M. Shabab Hossain, Md. Mahmudur Rahman, M. Sohel Rahman

Lecture notes in computer science•Jan 1, 2011•0 citations

Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem

Shasha Wang, Hailing Liu, Yan-Qi Song +3 more

•Jan 1, 2023•0 citations

Quantum alternating operator ansatz for solving the minimum exact cover problem

Shasha Wang, Hailing Liu, Yan-Qi Song +3 more

Physica A Statistical Mechanics and its Applications•Jul 22, 2023•19 citations

Quantum-Assisted Recursive Algorithm for Solving the Exact Cover Problem

Xiao‐Hui Ni, Jia-Cheng Fan, Ling‐Xiao Li +5 more

arXiv:2509.10811•Chinese Journal of Physics•Nov 1, 2026•2 citations

Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem

Shasha Wang, Hailing Liu, Su‐Juan Qin +2 more

The Quantum Alternating Operator Ansatz (QAOA+) is an extension of the Quantum Approximate Optimization Algorithm (QAOA), where the search space is smaller in solving constrained combinatorial optimization problems. However, QAOA+ requires a trivial feasible solution as the initial state, so it cannot be used for problems that are difficult to find a trivial feasible solution. For simplicity, we call them as Non-Trivial-Feasible-Solution Problems (NTFSP). In this paper, we take the Minimum Exact Cover (MEC) problem as an example, studying how to apply QAOA+ to NTFSP. As we know, exact covering (EC) is the feasible space of MEC problem, which has no trivial solutions. To overcome the above problem, the EC problem is divided into two steps to solve. First, disjoint sets are obtained, which is equivalent to solving independent sets. Second, on this basis, the sets covering all elements (i.e., EC) are solved. In other words, we transform MEC into a multi-objective constrained optimization problem, where feasible space consists of independent sets that are easy to find. Finally, we also verify the feasibility of the algorithm from numerical experiments. Our method provides a feasible way for applying QAOA+ to NTFSP, and is expected to expand its application significantly.

arXiv:2211.15266•Nov 28, 2022•0 citations

Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search

Sebastian Senge

We give quantum algorithms for exponential-time problems on $n$ vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time $O(1.3032^n)$, from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, $O(1.3100^n)$. The previous best bound in this model, to our knowledge, is $O(1.3231^n)$. (2) $k$-Colouring below the previous best bound for $k \in \{5, 7, 8, 9, 10, 11\}$ and $13 \le k \le 18$, from $O(1.4518^n)$ for $k = 5$ to $O(1.9233^n)$ for $k = 18$. (3) Dominating Set in $O(1.2235^n)$, against the previous $O(2^{n/2})$, Independent Dominating Set in $O(1.1583^n)$, and Edge Dominating Set and Minimum Maximal Matching in $O(1.1501^n)$. (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with $c^k$ nodes up to polynomial factors, the problem is solved in quantum time $(2 - 1/c)^{n/2}$ up to polynomial factors. This gives Feedback Vertex Set in $O(1.3081^n)$, Subset and Group Feedback Vertex Set in $O(1.3229^n)$, Cluster Vertex Deletion in $O(1.2033^n)$, 3-Hitting Set in $O(1.2405^n)$, Proper Interval Vertex Deletion in $O(1.3541^n)$, Multicut on Trees in $O(1.1647^n)$ and Min-Ones $d$-SAT in $O^*((2-1/d)^{n/2})$. (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in $O(1.0555^n)$ and for Feedback Vertex Set in $O(1.2161^n)$. The colouring exponents for $k \ge 6$ come from an evaluation of a known reduction recursion, computed in floating point with a margin.

arXiv:2611.12714•Nov 9, 2026•0 citations
The Quantum Alternating Operator Ansatz (QAOA+) is an extension of the Quantum Approximate Optimization Algorithm (QAOA), where the search space is smaller in solving constrained combinatorial optimization problems. However, QAOA+ requires a trivial feasible solution as the initial state, so it cannot be used for problems that are difficult to find a trivial feasible solution. For simplicity, we call them as Non-Trivial-Feasible-Solution Problems (NTFSP). In this paper, we take the Minimum Exact Cover (MEC) problem as an example, studying how to apply QAOA+ to NTFSP. As we know, exact covering (EC) is the feasible space of MEC problem, which has no trivial solutions. To overcome the above problem, the EC problem is divided into two steps to solve. First, disjoint sets are obtained, which is equivalent to solving independent sets. Second, on this basis, the sets covering all elements (i.e., EC) are solved. In other words, we transform MEC into a multi-objective constrained optimization problem, where feasible space consists of independent sets that are easy to find. Finally, we also verify the feasibility of the algorithm from numerical experiments. Our method provides a feasible way for applying QAOA+ to NTFSP, and is expected to expand its application significantly.
We give quantum algorithms for exponential-time problems on nnn vertices or elements, with bounded error, polynomial space and no quantum random access memory. Our results are these. (1) 4-Colouring in quantum time O(1.3032n)O(1.3032^n)O(1.3032n), from a polynomial-space branching algorithm with polynomial-space terminal algorithms; with the branching algorithm alone, O(1.3100n)O(1.3100^n)O(1.3100n). The previous best bound in this model, to our knowledge, is O(1.3231n)O(1.3231^n)O(1.3231n). (2) kkk-Colouring below the previous best bound for k∈{5,7,8,9,10,11}k \in \{5, 7, 8, 9, 10, 11\}k∈{5,7,8,9,10,11} and 13≤k≤1813 \le k \le 1813≤k≤18, from O(1.4518n)O(1.4518^n)O(1.4518n) for k=5k = 5k=5 to O(1.9233n)O(1.9233^n)O(1.9233n) for k=18k = 18k=18. (3) Dominating Set in O(1.2235n)O(1.2235^n)O(1.2235n), against the previous O(2n/2)O(2^{n/2})O(2n/2), Independent Dominating Set in O(1.1583n)O(1.1583^n)O(1.1583n), and Edge Dominating Set and Minimum Maximal Matching in O(1.1501n)O(1.1501^n)O(1.1501n). (4) A quantum form of monotone local search: if the extension problem has a backtracking tree with ckc^kck nodes up to polynomial factors, the problem is solved in quantum time (2−1/c)n/2(2 - 1/c)^{n/2}(2−1/c)n/2 up to polynomial factors. This gives Feedback Vertex Set in O(1.3081n)O(1.3081^n)O(1.3081n), Subset and Group Feedback Vertex Set in O(1.3229n)O(1.3229^n)O(1.3229n), Cluster Vertex Deletion in O(1.2033n)O(1.2033^n)O(1.2033n), 3-Hitting Set in O(1.2405n)O(1.2405^n)O(1.2405n), Proper Interval Vertex Deletion in O(1.3541n)O(1.3541^n)O(1.3541n), Multicut on Trees in O(1.1647n)O(1.1647^n)O(1.1647n) and Min-Ones ddd-SAT in O∗((2−1/d)n/2)O^*((2-1/d)^{n/2})O∗((2−1/d)n/2). (5) Quantum exponential-time approximations below the quantum exact bounds, such as a 1.1-approximation for Vertex Cover in O(1.0555n)O(1.0555^n)O(1.0555n) and for Feedback Vertex Set in O(1.2161n)O(1.2161^n)O(1.2161n). The colouring exponents for k≥6k \ge 6k≥6 come from an evaluation of a known reduction recursion, computed in floating point with a margin.