CS Paper Radar

On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry

Dmitrii Chemodanov

cs.NI quant-ph ·submitted 2026-11-11 18:08 UTC · v1
theory

Abstract

Finding a path whose totals under several additive metrics all fall inside prescribed ranges is weakly NP-complete. We ask what two quantum algorithms can do for it, against strong classical baselines. For directed acyclic graphs (DAGs) we give a Grover search whose state preparation builds the uniform superposition over all source-to-destination paths with one qubit per arc and no ancilla. We prove it correct, give its exact gate count, and show that measured strings form an error- detecting code whose distance is a girth-like graph parameter. We complete the oracle and count its gates: one search on our largest instance, 136 arc qubits and 262,144 paths, needs about 4.4 x 10^5 Toffoli gates, while classical dynamic programming decides the same instance with 18,754 labels. Grover search needs O(sqrt(N/M)) oracle calls for M good paths among N . Classical meet-in-the-middle matches this exponent in the worst case, and known quantum algorithms with quantum memory beat it. For a staged fabric with node-independent linear weights, maximizing the number of satisfied metrics is max-LINSAT, and with power- of-index weights it is Optimal Polynomial Intersection, where no known polynomial-time classical algorithm matches decoded quantum interferometry (DQI). We verify this translation in simulation and run two small binary instances on IBM Heron processors, which keep 67 % and 15 % of the ideal gain over uniform sampling.

Closest papers

Nearest neighbours by meaning across the whole index.

Hardness of Pathfinding in a Welded Tree

cs.CC quant-ph ·2026-09-17 ·David Miloschewsky, Supartha Podder
theory similarity 0.72
Abstract · 55 pages, 4 figures

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

0.29

Resource-Aware Grover Search for Minimum Vertex Cover

cs.ET quant-ph ·2026-10-05 ·Beilei Jiang, Harry Fu, Pavan Krishna Yarlagadda, Alexander Shan, Yunhe Feng +1 more
similarity 0.68
Abstract · 13 pages, 12 figures

The Minimum Vertex Cover (MVC) problem is a fundamental NP-hard combinatorial optimization problem with applications in network analysis and resource allocation. Grover's algorithm provides a quadratic reduction in query complexity for unstructured search, but existing Grover-based MVC formulations can incur substantial quantum resource overhead due to costly vertex-counting circuits and complex oracle constructions. We develop and evaluate several encoding and oracle-design strategies for reducing the qubit count, circuit depth, and gate complexity of Grover-based MVC search. First, we construct a Dicke-Parallel formulation that restricts the search to fixed-cardinality subsets, eliminating explicit vertex counting, together with a parallel edge-verification oracle that reduces feasibility-checking overhead. We then develop an Edge-Counting formulation that replaces per-edge auxiliary storage with a logarithmic-size counting register, substantially reducing ancillary-qubit requirements. Finally, we propose an Edge-Centric encoding that represents endpoint selections directly and derives vertex-selection states through incident-edge Boolean operations, enabling more depth-efficient oracle construction. Our resource analysis reveals complementary trade-offs among qubit width, circuit depth, gate count, and Grover iteration count. Edge-Counting is particularly attractive under tight qubit constraints, while Edge-Centric can reduce both circuit depth and Grover iteration count when the graph has a moderate edge count and sufficient representation multiplicity. Dicke-Parallel provides a more robust choice when such multiplicity is limited or graph density makes the edge-based search space large. These results provide practical guidance for selecting Grover-based MVC formulations according to hardware constraints and graph structure.

0.14

A Grover-Amplified Oracle for Maximum Clique on Graph, Minimum Hitting set and Dualizations on Hypergraphs Built on Quantum Phase Estimation

cs.CC quant-ph ·2026-11-07 ·Francisco Piñero, Fernando L. \Pelayo, Hernan I. de la Cruz, Jose J. Paulet, Mauro Mezzini +1 more
similarity 0.66
Abstract

In this paper, we use a quantum circuit called the Graph Encoding Operator which, applied to the complement $\bar G$ of any graph $G$, yields an oracle for the maximum clique problem suitable for amplification via Grover's algorithm. Analogously, we devise a Hypergraph Encoding Operator which, when applied to a hypergraph $\mathcal H$, yields an oracle for the minimum hitting set suitable for amplification via Grover's algorithm. Interestingly, the latter oracle provides, when measured, an approximation of the number of hitting sets of the hypergraph, thus solving the dualization problem for positive Boolean functions represented in a positive irredundant disjunctive normal form. We give the full construction of both operators, prove their correctness, analyze their complexity, and provide an implementation on a quantum simulator. We discuss the resulting complexity, contrast them with existing quantum computer algorithms based on Grover search and we will show that our algorithms outperform, to the best of our knowledge, all of the previous algorithms on space computational complexity by requiring only $O(N)$ number of qubits with respect to the number of vertices $N$, for representing both graphs and hypergraphs in the encoding operator and, consequently, results in an oracle for both graphs and hypergraphs that uses only $O(N)$ qubits even when the hypergraph contains an exponential (on the number of vertices) number of hyperedges.

0.29

A Quantum Lower Bound for Triangle Finding

cs.DS quant-ph ·2026-11-04 ·Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou
theory similarity 0.66
Abstract · 37 pages

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.

0.48

Gate-level Implementation and Resource Analysis of Lackadaisical Quantum Walk Search

cs.ET quant-ph ·2026-08-17 ·Amit Saha, Debanjan Kola, Nishanka Das, Amlan Chakrabarti
similarity 0.65
Abstract · 27 pages, 15 figures

Lackadaisical quantum walks (LQW) extend discrete-time quantum walks (DTQW) by introducing weighted self-loops, enabling improved spatial-search performance through controlled localization of the walker. Despite substantial theoretical progress, practical gate-level implementations suitable for quantum hardware remain largely unexplored, limiting evaluation under realistic architectural constraints, noise, and resource requirements. In this work, we present a gate-level implementation framework for lackadaisical quantum walk search. The proposed construction encodes the position and coin spaces into qubit registers, and realizes the walk dynamics through oracle, coin, and flip-flop shift operations. We validate the circuit by reproducing the expected search behavior for single and multiple marked vertices and by analyzing the effect of the self-loop weight on the success probability. We further evaluate the implementation under realistic noisy settings using superconducting hardware's noise models. Logical resource analysis shows that, for grids ranging from $8\times8$ to $64\times64$, the transpiled gate count increases from $3.63\times10^{5}$ to $4.38\times10^{6}$ and the circuit depth from $2.13\times10^{5}$ to $2.56\times10^{6}$. Finally, fault-tolerant resource estimates based on a surface-code model using the Microsoft Quantum Resource Estimator demonstrate the substantial space-time trade-off associated with magic-state production. The results establish a practical circuit-level pathway for implementing the LQW search and provide a basis for evaluating its performance.

0.29

Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition

cs.DS quant-ph ·2026-08-24 ·John Burke, Ciaran McGoldrick
similarity 0.64
Abstract · 28 pages, 3 figures

Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal $Θ(\sqrt{N})$ oracle and non-oracle gate counts. For spatial search on $d$-dimension grids, it recovers the $O(\sqrt{N})$ time for $d\geq3$ and the $O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$ bound of Aaronson and Ambainis for $d=2$. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.

0.43

Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction

cs.DS quant-ph ·2026-10-07 ·Aayra Dhindsa Sawkmie
similarity 0.64
Abstract · 12 pages, 2 figures

The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold $K$ and a promised fraction $p$, decide whether at least a fraction $p$ of all tours have total length at most $K$, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using $O(1/\sqrt{p})$ oracle queries, independent of the number of cities $N$, with each query implemented by a quantum circuit of polynomial size in $N$. For any fixed robustness level $p$, the total runtime is therefore polynomial in $N$. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on $1/p$ over classical random sampling, which needs $Θ(1/p)$ samples; because each quantum query is costly, however, it is faster in total running time only when $p$ is very small (roughly below $N^{-4}$), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.

0.15

Clifford synthesis is NP-complete

cs.CC quant-ph ·2026-10-29 ·Søren Fuglede Jørgensen
similarity 0.64
Abstract

We show that the problem of synthesizing a quantum circuit for a given Clifford operator using at most a specified amount of resources is NP-complete for several resource models of practical interest. Specifically, we study synthesis of a given Clifford operator using single-qubit Clifford gates and two-qubit Clifford gates, with full qubit connectivity and no additional ancilla qubits. With single-qubit gates free and CNOT as the only two-qubit gate, we show that deciding whether a given target admits an implementation using at most a specified number of CNOT gates is NP-complete, and we show that the problem remains NP-complete when any two-qubit Clifford gate is allowed and the budget counts all such gates. Moreover, we show that both results continue to hold when SWAP gates may be inserted for free, and when single-qubit gates are also considered part of the budget. In each case, we build on recent work by Li and Guan and show that there are polynomial-time reductions from Hamiltonian path in grid graphs to these decision problems, using a number of qubits quadratic in the number of grid vertices.

0.05