28 citations · 63 across the 9 of their papers we have counts for
3 papers · 1 filter
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…
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…