Publications (14)
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…
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…
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…
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…
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…
Matching Triangles and Triangle Collection: Hardness based on a Weak Quantum Conjecture
Andris Ambainis, Harry Buhrman, Koen Leijnse +2
Classically, for many computational problems one can conclude time lower bounds conditioned on the hardness of one or more of key problems: k-SAT, 3SUM and APSP. More recently, sim…
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…
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…
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…
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…
Oracle Separations for RPH
Thekla Hamm, Lucas Meijer, Tillmann Miltzow +1
While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real…
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…
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…