122 citations · 289 across the 18 of their papers we have counts for
4 papers · 2 filters
A single-shot measurement of the energy of product states in a translation invariant spin chain can replace any quantum computation
Dominik Janzing, Pawel Wocjan, Shengyu Zhang
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a on…
Efficient Quantum Algorithm for Identifying Hidden Polynomials
Thomas Decker, Jan Draisma, Pawel Wocjan
We consider a natural generalization of an abelian Hidden Subgroup Problem where the subgroups and their cosets correspond to graphs of linear functions over a finite field F with…
A PromiseBQP-complete String Rewriting Problem
Dominik Janzing, Pawel Wocjan
We are given three strings s, t, and t' of length L over some fixed finite alphabet and an integer m that is polylogarithmic in L. We have a symmetric relation on substrings of con…
Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
Thomas Decker, Pawel Wocjan
We introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem (HSP) where the subgroups and their cosets correspond to…