17 citations · 61 across the 16 of their papers we have counts for
18 papers
Characterizing Quantum Advantage for Generalizations of the Boolean Hidden Matching Problem
Mark Bun, Joao F. Doriguello, John Kallaugher +1
We study the one-way communication complexity of the -Boolean Hidden Partition problem. Here, Alice is given an -bit string and Bob is given disjoint blocks of its ind…
Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
Joao F. Doriguello
Reinforcement learning is a subfield of machine learning that studies how an agent interacts with an environment in order to extract as large a reward as possible. A standard appro…
Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos +1
Bell sampling is a simple yet powerful tool based on measuring two copies of a quantum state in the Bell basis, and has found applications in a plethora of problems related to stab…
A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
Andris Ambainis, Joao F. Doriguello, Debbie Lim
We propose novel classical and quantum online algorithms for learning finite- and infinite-horizon Markov Decision Processes (MDPs). Our algorithms are based on a hybrid online-off…
On the practicality of quantum sieving algorithms for the shortest vector problem
Joao F. Doriguello, George Giapitzakis, Alessandro Luongo +1
One of the main candidates of post-quantum cryptography is lattice-based cryptography. Its cryptographic security against quantum attackers is based on the worst-case hardness of l…
Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
Jonathan Allcock, Joao F. Doriguello, Gábor Ivanyos +1
Bell sampling is a simple yet powerful measurement primitive that has recently attracted a lot of attention, and has proven to be a valuable tool in studying stabiliser states. Unf…
Quantum generalizations of Glauber and Metropolis dynamics
András Gilyén, Chi-Fang Chen, Joao F. Doriguello +1
Classical Markov Chain Monte Carlo methods have been essential for simulating statistical physical systems and have proven well applicable to other systems with many degrees of fre…
Quantum Algorithms for the Pathwise Lasso
Joao F. Doriguello, Debbie Lim, Chi Seng Pun +2
We present a novel quantum high-dimensional linear regression algorithm with an -penalty based on the classical LARS (Least Angle Regression) pathwise algorithm. Similarly…
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…
Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
Jonathan Allcock, Jinge Bao, Joao F. Doriguello +2
We explore the power of the unbounded Fan-Out gate and the Global Tunable gates generated by Ising-type Hamiltonians in constructing constant-depth quantum circuits, with particula…
Hybrid Quantum-Classical Algorithm For Robust Optimization via Stochastic-Gradient Online Learning
Debbie Lim, Joao F. Doriguello, Patrick Rebentrost
Optimization theory has been widely studied in academia and finds a large variety of applications in industry. The different optimization models in their discrete and/or continuous…
Decoding probabilistic syndrome measurement and the role of entropy
João F. Doriguello
In realistic stabiliser-based quantum error correction there are many ways in which real physical systems deviate from simple toy models of error. Stabiliser measurements may not a…
A note on the partition bound for one-way classical communication complexity
Srinivasan Arunachalam, João F. Doriguello, Joao F. Doriguello +1
We present a linear program for a one-way version of the partition bound of Jain and Klauck, denoted , and show that it characterizes the one-way ran…
Quantum algorithm for stochastic optimal stopping problems with applications in finance
João F. Doriguello, Alessandro Luongo, Jinge Bao +2
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in stochastic optimal stopp…
Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
Srinivasan Arunachalam, Joao F. Doriguello
We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful -uniform convexity…
Quantum Random Access Codes for Boolean Functions
João F. Doriguello, Ashley Montanaro
An random access code (RAC) is an encoding of bits into bits such that any initial bit can be recovered with probability at least , while in a q…
Exponential quantum communication reductions from generalizations of the Boolean Hidden Matching problem
João F. Doriguello, Ashley Montanaro
In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-qu…
Quantum sketching protocols for Hamming distance and beyond
João F. Doriguello, Ashley Montanaro
In this work we use the concept of quantum fingerprinting to develop a quantum communication protocol in the simultaneous message passing model that calculates the Hamming distance…