225 citations · 582 across the 52 of their papers we have counts for
61 papers
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…
Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
Divesh Aggarwal, Antoine Joux, Miklos Santha +1
The Unbounded Subset Sum (USS) problem is an NP-hard computational problem where the goal is to decide whether there exist non-negative integers such that $x_1 a…
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…