8 papers
Subcube Stifling
Arjan Cornelissen, Nikhil S. Mande, Nithish Raja
We introduce the subcube stifling number, a new combinatorial measure of total Boolean functions. This measure is the largest integer such that, for every set of at most $k…
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 algorithms through graph composition
Arjan Cornelissen
In this work, we unify several quantum algorithmic frameworks for boolean functions that are based on the quantum adversary bound. First, we show that the -connectivity framewo…
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…
Randomized and quantum approximate matrix multiplication
Simon Apers, Arjan Cornelissen, Samson Wang
The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers…
Quantum walks through generalized graph composition
Arjan Cornelissen
In this work, we generalize the recently-introduced graph composition framework to the non-boolean setting. A quantum algorithm in this framework is represented by a hypergraph, wh…