Problems in the class NP are important in computational science, where a given candidate solution can be verified in polynomial time, while finding a solution may require evaluating the entire search space in the worst case. Classical exhaustive approaches generally solve such problems by evaluating the verifier function over all possible inputs, resulting in a worst-case query complexity of O(N), where N = d^n represents the size of the search space, d is the number of possible values for each variable, and n is the number of variables. Quantum search algorithms can solve unstructured search problems more efficiently by reducing the query complexity to O(sqrt (N)), providing a quadratic speedup over classical exhaustive search. However, conventional quantum search formulations typically assume access to an oracle that identifies valid solutions, while standard implementations generally yield probabilistic success. In this work, we propose a generalised quantum oracle construction method for NP problems, together with a deterministic quantum search framework that identifies satisfying assignments using their corresponding classical verifier functions. The proposed framework retains the quadratic query speedup of quantum search over classical exhaustive search. We further establish that constructed oracle can be implemented using a number of gates polynomial in the size (L) of the binary encoding of verification function, consistent with the polynomial-time evaluation of the corresponding classical verifier, while the total qubit requirement remains O(poly(L)). The construction is demonstrated on multiple N-SAT instances, with circuit-level simulations confirming deterministic identification of satisfying assignments. These results establish the applicability of deterministic quantum search to NP problems while retaining the quadratic query advantage over classical exhaustive search.
Problems in the class NP are important in computational science, where a given candidate solution can be verified in polynomial time, while finding a solution may require evaluating the entire search space in the worst case. Classical exhaustive approaches generally solve such problems by evaluating the verifier function over all possible inputs, resulting in a worst-case query complexity of O(N), where N = d^n represents the size of the search space, d is the number of possible values for each variable, and n is the number of variables. Quantum search algorithms can solve unstructured search problems more efficiently by reducing the query complexity to O(sqrt (N)), providing a quadratic speedup over classical exhaustive search. However, conventional quantum search formulations typically assume access to an oracle that identifies valid solutions, while standard implementations generally yield probabilistic success. In this work, we propose a generalised quantum oracle construction method for NP problems, together with a deterministic quantum search framework that identifies satisfying assignments using their corresponding classical verifier functions. The proposed framework retains the quadratic query speedup of quantum search over classical exhaustive search. We further establish that constructed oracle can be implemented using a number of gates polynomial in the size (L) of the binary encoding of verification function, consistent with the polynomial-time evaluation of the corresponding classical verifier, while the total qubit requirement remains O(poly(L)). The construction is demonstrated on multiple N-SAT instances, with circuit-level simulations confirming deterministic identification of satisfying assignments. These results establish the applicability of deterministic quantum search to NP problems while retaining the quadratic query advantage over classical exhaustive search.
Quantum query complexity underpins much of our understanding of quantum speedups, yet nearly all existing lower and upper bounds are derived for simple Boolean oracles. Many practical tasks-noisy database search, stochastic optimization, adaptive learning, and time-varying systems-are best modeled by richer oracle classes. This paper systematically extends quantum query complexity theory to four non-standard oracle models: (1) stochastic oracles that return random outputs drawn from a distribution; (2) multi-solution oracles encoding a solution set of size k; (3) time-dependent oracles whose internal state evolves between queries; and (4) relational oracles encoding structured constraints rather than simple membership. Using generalized adversary methods, polynomial method techniques, and hybrid arguments, we derive tight (up to polylog factors) lower bounds for each model and construct matching algorithms where possible. For instance, we show that searching for any one of k marked items in an unstructured database still admits a Grover-like quadratic speedup, but with optimal complexity Θ(N/k), and that stochastic noise in oracle outputs degrades the advantage gracefully as a function of the noise parameter. For certain time-dependent and relational models, we prove that no better-than-classical speedup is possible, clarifying the limits of quantum advantage in adaptive settings. These results provide a more realistic foundation for quantum algorithms targeting noisy search, stochastic optimization, and constraint satisfaction, and they highlight the precise structural features that enable or preclude query-based quantum speedups.
Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms across a broad class of unstructured search problems.The original protocol is probabilistic, returning the desired result with significant probability on each query but, in general, requiring several iterations of the algorithm.We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.Our deterministic, two-parameter "D2p" protocol utilizes generalized phase rotations replacing the phase inversions after a standard oracle query.The D2p protocol achieves a 100% success rate in no more than one additional iteration compared to the optimal number of steps as in the original Grover's search enabling the same quadratic speedup.We also provide a visualization using the Bloch sphere for enhanced geometric intuition.
We present an exact quantum algorithm for solving the Exact Satisfiability problem, which belongs to the important NP-complete complexity class. The algorithm is based on an intuitive approach that can be divided into two parts: the first step consists in the identification and efficient characterization of a restricted subspace that contains all the valid assignments of the Exact Satisfiability; while the second part performs a quantum search in such restricted subspace. The quantum algorithm can be used either to find a valid assignment (or to certify that no solution exists) or to count the total number of valid assignments. The query complexities for the worst-case are respectively bounded by and , where n is the number of variables and the number of linearly independent clauses. Remarkably, the proposed quantum algorithm results to be faster than any known exact classical algorithm to solve dense formulas of Exact Satisfiability. As a concrete application, we provide the worst-case complexity for the Hamiltonian cycle problem obtained after mapping it to a suitable Occupation problem. Specifically, we show that the time complexity for the proposed quantum algorithm is bounded by for 3-regular undirected graphs, where n is the number of nodes. The same worst-case complexity holds for -regular bipartite graphs. As a reference, the current best classical algorithm has a (worst-case) running time bounded by . Finally, when compared to heuristic techniques for Exact Satisfiability problems, the proposed quantum algorithm is faster than the classical WalkSAT and Adiabatic Quantum Optimization for random instances with a density of constraints close to the satisfiability threshold, the regime in which instances are typically the hardest to solve. The proposed quantum algorithm can be straightforwardly extended to the generalized version of the Exact Satisfiability known as Occupation problem. The general version of the algorithm is presented and analyzed.
We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches. Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations, a key limitation of other deterministic methods. The algorithm achieves certainty by recursively expanding the base oracle so that it marks all states prefixed by the same two bits as the target, encompassing exactly one-quarter of the search space. This enables a step-by-step reduction of the superposition until the target state can be measured with certainty. The algorithm achieves deterministic success with a query complexity of O(Nlog2(3)/2)≈O(N0.7925), falling between Grover's O(N) scaling and the classical O(N). Our approach relies exclusively on two-qubit nearest-neighbour diffusion operators, avoiding global diffusion entirely. We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits, with even greater advantages on hardware with limited qubit connectivity. The scheme's inherent determinism, reliance on simple nearest-neighbour, low-depth operations, and scalable recursive structure make it well-suited for hardware implementation. Additionally, we show that the algorithm naturally supports partial database search, enabling deterministic identification of selected target bits without requiring a full search, further broadening its applicability.
We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as PNP and PQMA, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes PNP[log] and PQMA[log], defined identically to PNP and PQMA, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a PNP machine have a "query graph" which is a tree, then this computation can be simulated in PNP[log]. In this work, we first show that for any verification class C∈{NP,MA,QCMA,QMA,QMA(2),NEXP,QMAexp}, any PC machine with a query graph of "separator number" s can be simulated using deterministic time exp(slogn) and slogn queries to a C-oracle. When s∈O(1) (which includes the case of O(1)-treewidth, and thus also of trees), this gives an upper bound of PC[log], and when s∈O(logk(n)), this yields bound QPC[logk+1] (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding PC computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial p specified via an arithmetic circuit, if one can "weakly compress" p so that its optimal value requires m bits to represent, then PNP can be decided with only m queries to an NP-oracle.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.