225 citations · 582 across the 52 of their papers we have counts for
40 papers · 1 filter
The quantum query complexity of the semigroup product problem
Troy Lee, Miklos Santha
We study the quantum query complexity of computing a semigroup product , when one query reveals one input element and the multiplication table is given. For a finite…
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…
On generating direct powers of dynamical Lie algebras
Jonathan Allcock, Miklos Santha, Pei Yuan +1
The expressibility and trainability of parameterized quantum circuits has been shown to be intimately related to their associated dynamical Lie algebras (DLAs). From a quantum algo…
Quasi-quantum states and the quasi-quantum PCP theorem
Itai Arad, Miklos Santha
We introduce -local quasi-quantum states: a superset of the regular quantum states, defined by relaxing the positivity constraint. We show that a -local quasi-quantum state o…
On the dynamical Lie algebras of quantum approximate optimization algorithms
Jonathan Allcock, Miklos Santha, Pei Yuan +1
Dynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits, helping to characterize both their expressiveness and trainability. In…
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…
On the quantum time complexity of divide and conquer
Jonathan Allcock, Jinge Bao, Aleksandrs Belovs +2
We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimi…
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…
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…
Classical and Quantum Algorithms for Variants of Subset-Sum via Dynamic Programming
Jonathan Allcock, Yassine Hamoudi, Antoine Joux +2
Subset-Sum is an NP-complete problem where one must decide if a multiset of integers contains a subset whose elements sum to a target value . The best-known classical and qu…
Quantum Alphatron: quantum advantage for learning with kernels and noise
Siyi Yang, Naixu Guo, Miklos Santha +1
At the interface of machine learning and quantum computing, an important question is what distributions can be learned provably with optimal sample complexities and with quantum-ac…
Characterizing the intersection of QMA and coQMA
Serge Massar, Miklos Santha
We show that the functional analogue of QMAcoQMA, denoted F(QMAcoQMA), equals the complexity class Total Functional QMA (TFQMA). To prove this we need to introduce alte…
Quantum algorithms for hedging and the learning of Ising models
Patrick Rebentrost, Yassine Hamoudi, Maharshi Ray +3
A paradigmatic algorithm for online learning is the Hedge algorithm by Freund and Schapire. An allocation into different strategies is chosen for multiple rounds and each round inc…
Discrete logarithm and Diffie-Hellman problems in identity black-box groups
Gabor Ivanyos, Antoine Joux, Miklos Santha
We investigate the computational complexity of the discrete logarithm, the computational Diffie-Hellman and the decisional Diffie-Hellman problems in some identity black-box groups…
Strategies for quantum races
Troy Lee, Maharshi Ray, Miklos Santha
We initiate the study of quantum races, games where two or more quantum computers compete to solve a computational problem. While the problem of dueling algorithms has been studied…
On learning linear functions from subset and its applications in quantum computing
Gábor Ivanyos, Anupam Prakash, Miklos Santha
Let be the finite field of size and let be a linear function. We introduce the {\em Learning From Subset} problem LFS$(q,…
Total Functions in QMA
Serge Massar, Miklos Santha
The complexity class QMA is the quantum analog of the classical complexity class NP. The functional analogs of NP and QMA, called functional NP (FNP) and functional QMA (FQMA), con…
Quantum attacks on Bitcoin, and how to protect against them
Divesh Aggarwal, Gavin K. Brennen, Troy Lee +2
The key cryptographic protocols used to secure the internet and financial transactions of today are all susceptible to attack by the development of a sufficiently large quantum com…
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5
While exponential separations are known between quantum and randomized communication complexity for partial functions (Raz, STOC 1999), the best known separation between these meas…
Linear time algorithm for quantum 2SAT
Itai Arad, Miklos Santha, Aarthi Sundaram +1
A canonical result about satisfiability theory is that the 2-SAT problem can be solved in linear time, despite the NP-hardness of the 3-SAT problem. In the quantum 2-SAT problem, w…
Nonlocality and conflicting interest games
Anna Pappa, Niraj Kumar, Thomas Lawson +4
Nonlocality enables two parties to win specific games with probabilities strictly higher than allowed by any classical theory. Nevertheless, all known such examples consider games…
An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group
Thomas Decker, Gábor Ivanyos, Raghav Kulkarni +2
In the theory of algebraic groups, parabolic subgroups form a crucial building block in the structural studies. In the case of general linear groups over a finite field , give…
Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
Thomas Decker, Peter Hoyer, Gabor Ivanyos +1
We present a new method for solving the hidden polynomial graph problem (HPGP) which is a special case of the hidden polynomial problem (HPP). The new approach yields an efficient…
Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing
Troy Lee, Frederic Magniez, Miklos Santha
We show that the quantum query complexity of detecting if an -vertex graph contains a triangle is . This improves the previous best algorithm of Belovs making $O(n^{…