28 citations · 63 across the 9 of their papers we have counts for
12 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…
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…
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…
Teleportation of quantum coherence
Sohail, Arun K Pati, Vijeth Aradhya +2
We investigate whether it is possible to teleport the coherence of an unknown quantum state from Alice to Bob by communicating a lesser number of classical bits in comparison to wh…
Memory Compression with Quantum Random-Access Gates
Harry Buhrman, Bruno Loff, Subhasree Patro +1
In the classical RAM, we have the following useful property. If we have an algorithm that uses memory cells throughout its execution, and in addition is sparse, in the sense th…
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…
Limits of quantum speed-ups for computational geometry and other problems: Fine-grained complexity via quantum walks
Harry Buhrman, Bruno Loff, Subhasree Patro +1
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n^3)-time or O(n^2)-time classic algorithm can be solved by a known O(n^1.5…
The Quantum Strong Exponential-Time Hypothesis
Harry Buhrman, Subhasree Patro, Florian Speelman
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability wit…
Impossibility of Cloning of Quantum Coherence
Dhrumil Patel, Subhasree Patro, Chiranjeevi Vanarasa +2
It is well known that it is impossible to clone an arbitrary quantum state. However, this inability does not lead directly to no-cloning of quantum coherence. Here, we show that it…
Non-negativity of conditional von Neumann entropy and global unitary operations
Subhasree Patro, Indranil Chakrabarty, Nirman Ganguly
Conditional von Neumann entropy is an intriguing concept in quantum information theory. In the present work, we examine the effect of global unitary operations on the conditional e…