211 citations · 1.2k across the 74 of their papers we have counts for
54 papers · 1 filter
Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence
Pawel Wocjan
We give a quantum algorithm for a novel type of black-box problem: identifying a hidden -regular base graph on vertices from oracle access to an obfuscated version of it…
Quantized Markov Chain Couplings that Prepare Qsamples
Kristan Temme, Pawel Wocjan
We present a novel approach to quantizing Markov chains. The approach is based on the Markov chain coupling method, which is frequently used to prove fast mixing. Given a particula…
Controlization Schemes Based on Orthogonal Arrays
Anirban Chowdhury, Ewout van den Berg, Pawel Wocjan
Realizing controlled operations is fundamental to the design and execution of quantum algorithms. In quantum simulation and learning of quantum many-body systems, an important subr…
Techniques for learning sparse Pauli-Lindblad noise models
Ewout van den Berg, Pawel Wocjan
Error-mitigation techniques such as probabilistic error cancellation and zero-noise extrapolation benefit from accurate noise models. The sparse Pauli-Lindblad noise model is one o…
Thermal State Preparation via Rounding Promises
Patrick Rall, Chunhao Wang, Pawel Wocjan
A promising avenue for the preparation of Gibbs states on a quantum computer is to simulate the physical thermalization process. The Davies generator describes the dynamics of an o…
Space-efficient Quantization Method for Reversible Markov Chains
Chen-Fu Chiang, Anirban Chowdhury, Pawel Wocjan
In a seminal paper, Szegedy showed how to construct a quantum walk for any reversible Markov chain such that its eigenvector with eigenphase is a quantum sample of t…
Quantum-enhanced Markov chain Monte Carlo
David Layden, Guglielmo Mazzola, Ryan V. Mishmash +4
Sampling from complicated probability distributions is a hard computational problem arising in many fields, including statistical physics, optimization, and machine learning. Quant…
On the complexity of quantum partition functions
Sergey Bravyi, Anirban Chowdhury, David Gosset +1
The partition function and free energy of a quantum many-body system determine its physical properties in thermal equilibrium. Here we study the computational complexity of approxi…
Szegedy Walk Unitaries for Quantum Maps
Pawel Wocjan, Kristan Temme
Szegedy developed a generic method for quantizing classical algorithms based on random walks [Proceedings of FOCS, 2004, pp. 32-41]. A major contribution of his work was the constr…
Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions
Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini +2
We present classical and quantum algorithms for approximating partition functions of classical Hamiltonians at a given temperature. Our work has two main contributions: first, we m…
Improved bounded-strength decoupling schemes for local Hamiltonians
Adam D. Bookatz, Martin Roetteler, Pawel Wocjan
We address the task of switching off the Hamiltonian of a system by removing all internal and system-environment couplings. We propose dynamical decoupling schemes, that use only b…
Hamiltonian quantum simulation with bounded-strength controls
Adam D. Bookatz, Pawel Wocjan, Lorenza Viola
We propose dynamical control schemes for Hamiltonian simulation in many-body quantum systems that avoid instantaneous control operations and rely solely on realistic bounded-streng…
Recovering the Period in Shor's Algorithm with Gauss' Algorithm for Lattice Basis Reduction
Allison Koenecke, Pawel Wocjan
Shor's algorithm contains a classical post-processing part for which we aim to create an efficient, understandable method aside from continued fractions. Let r be an unknown positi…
Testing quantum expanders is co-QMA-complete
Adam D. Bookatz, Stephen P. Jordan, Yi-Kai Liu +1
A quantum expander is a unital quantum channel that is rapidly mixing, has only a few Kraus operators, and can be implemented efficiently on a quantum computer. We consider the pro…
Quantum Algorithm for Computing the Period Lattice of an Infrastructure
Felix Fontein, Pawel Wocjan
We present a quantum algorithm for computing the period lattice of infrastructures of fixed dimension. The algorithm applies to infrastructures that satisfy certain conditions. The…
Hidden Symmetry Subgroup Problems
Thomas Decker, Gábor Ivanyos, Miklos Santha +1
We advocate a new approach of addressing hidden structure problems and finding efficient quantum algorithms. We introduce and investigate the Hidden Symmetry Subgroup Problem (HSSP…
Quantum Algorithms for One-Dimensional Infrastructures
Pradeep Sarvepalli, Pawel Wocjan
Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over fi…
Efficient quantum processing of ideals in finite rings
Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi +1
Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|)…
Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
David Poulin, Pawel Wocjan
We present a quantum algorithm to prepare the thermal Gibbs state of interacting quantum systems. This algorithm sets a universal upper bound D^alpha on the thermalization time of…
Fast Amplification of QMA
Daniel Nagaj, Pawel Wocjan, Yong Zhang
Given a verifier circuit for a problem in QMA, we show how to exponentially amplify the gap between its acceptance probabilities in the `yes' and `no' cases, with a method that is…
Efficient quantum circuits for arbitrary sparse unitaries
Stephen P. Jordan, Pawel Wocjan
Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided…
Efficient Circuits for Quantum Walks
Chen-Fu Chiang, Daniel Nagaj, Pawel Wocjan
We present an efficient general method for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk. Our approach is based on Grover and Rudolph…
Quantum Speed-up for Approximating Partition Functions
Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe +1
We achieve a quantum speed-up of fully polynomial randomized approximation schemes (FPRAS) for estimating partition functions that combine simulated annealing with the Monte-Carlo…
Preparing ground states of quantum many-body systems on a quantum computer
David Poulin, Pawel Wocjan
Preparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustive…