6 papers · 1 filter
Quantum algorithms for path and cycle containment problems
Arjan Cornelissen, Amin Shiraz Gilani, Subhasree Patro
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph is present in an input graph , has been the subject of considerable study.…
Quantum Search With Generalized Wildcards
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string . An algorithm may, at unit cost…
Fine-Grained Complexity via Quantum Natural Proofs
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
Buhrman, Patro, and Speelman presented a framework of conjectures that together form a quantum analogue of the strong exponential-time hypothesis and its variants. They called it t…
QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
Yanlin Chen, Yilei Chen, Rajendra Kumar +2
While seemingly undesirable, it is not a surprising fact that there are certain problems for which quantum computers offer no computational advantage over their respective classica…
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction base…
Quantum Sabotage Complexity
Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro
Given a Boolean function , the goal in the usual query model is to compute on an unknown input while minimizing the number of queries t…