25 citations · 80 across the 15 of their papers we have counts for
19 papers
Improved quantum volume estimation with transducers and amortized quantum walks
Arjan Cornelissen, Simon Apers, Sander Gribling
The volume estimation problem is a classic task in computational geometry. The development of randomized algorithms for this problem spurred the development of many influential alg…
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 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…
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…
How to compute the volume in low dimension?
Arjan Cornelissen, Simon Apers, Sander Gribling
Estimating the volume of a convex body is a canonical problem in theoretical computer science. Its study has led to major advances in randomized algorithms, Markov chain theory, an…
Do you know what q-means?
Arjan Cornelissen, Joao F. Doriguello, Alessandro Luongo +1
Clustering is one of the most important tools for analysis of large datasets, and perhaps the most popular clustering algorithm is Lloyd's algorithm for -means. This algorithm t…
Quantum policy gradient algorithms
Sofiene Jerbi, Arjan Cornelissen, Māris Ozols +1
Understanding the power and limitations of quantum access to data in machine learning tasks is primordial to assess the potential of quantum computing in artificial intelligence. P…
Quantum tomography using state-preparation unitaries
Joran van Apeldoorn, Arjan Cornelissen, András Gilyén +1
We describe algorithms to obtain an approximate classical description of a -dimensional quantum state when given access to a unitary (and its inverse) that prepares it. For pure…
A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
Arjan Cornelissen, Yassine Hamoudi
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time with respect to the logarithm of the size of the state space. This is the first spee…
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…
Exact quantum query complexity of computing Hamming weight modulo powers of two and three
Arjan Cornelissen, Nikhil S. Mande, Maris Ozols +1
We study the problem of computing the Hamming weight of an -bit string modulo , for any positive integer whose only prime factors are 2 and 3. We show that the exa…
Near-Optimal Quantum Algorithms for Multivariate Mean Estimation
Arjan Cornelissen, Yassine Hamoudi, Sofiene Jerbi
We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at…
Quantum algorithms for multivariate Monte Carlo estimation
Arjan Cornelissen, Sofiene Jerbi
We consider the problem of estimating the expected outcomes of Monte Carlo processes whose outputs are described by multidimensional random variables. We tightly characterize the q…
Scalable Benchmarks for Gate-Based Quantum Computers
Arjan Cornelissen, Johannes Bausch, András Gilyén
In the near-term "NISQ"-era of noisy, intermediate-scale, quantum hardware and beyond, reliably determining the quality of quantum devices becomes increasingly important: users nee…
Span programs and quantum time complexity
Arjan Cornelissen, Stacey Jeffery, Maris Ozols +1
Span programs are an important model of quantum computation due to their tight correspondence with quantum query complexity. For any decision problem , the minimum complexity of…
Quantum gradient estimation of Gevrey functions
Arjan Cornelissen
Gradient-based numerical methods are ubiquitous in optimization techniques frequently applied in industry to solve practical problems. Often times, evaluating the objective functio…