Publications (55)
New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
Pawel Wocjan, Clive Elphick
Ergodic quantum computing
Dominik Janzing, Pawel Wocjan
Efficient Computation of the Permanent of Block Factorizable Matrices
Kristan Temme, Pawel Wocjan
Quantum Algorithm for Computing the Period Lattice of an Infrastructure
Felix Fontein, Pawel Wocjan
Performances of Block Codes Attaining the Expurgated and Cutoff Rate Lower Bounds on the Error Exponent of Binary Classical-Quantum Channels
Pawel Wocjan, Dejan E. Lazic, Thomas Beth
New Construction of Mutually Unbiased Bases in Square Dimensions
Pawel Wocjan, Thomas Beth
Bounds on the number of time steps for simulating arbitrary interaction graphs
Dominik Janzing, Pawel Wocjan, Thomas Beth
Complexity of decoupling and time-reversal for n spins with pair-interactions: Arrow of time in quantum control
Dominik Janzing, Pawel Wocjan, Thomas Beth
Unified spectral bounds on the chromatic number
Clive Elphick, Pawel Wocjan
Hamiltonian quantum simulation with bounded-strength controls
Adam D. Bookatz, Pawel Wocjan, Lorenza Viola
Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem
Andrew M. Childs, Aram W. Harrow, Pawel Wocjan
Efficient decoupling schemes with bounded controls based on Eulerian orthogonal arrays
Pawel Wocjan
BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
Dominik Janzing, Pawel Wocjan
The thermodynamic cost of reliability and low temperatures: Tightening Landauer's principle and the Second Law
Dominik Janzing, Pawel Wocjan, Robert Zeier +2
Improved bounded-strength decoupling schemes for local Hamiltonians
Adam D. Bookatz, Martin Roetteler, Pawel Wocjan
Efficient Circuits for Quantum Walks
Chen-Fu Chiang, Daniel Nagaj, Pawel Wocjan
The limitations of nice mutually unbiased bases
Michael Aschbacher, Andrew M. Childs, Pawel Wocjan
Speed-up via Quantum Sampling
Pawel Wocjan, Anura Abeyesinghe
Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer
David Poulin, Pawel Wocjan
The Jones polynomial: quantum algorithms and applications in quantum complexity theory
Pawel Wocjan, Jon Yard
Efficient quantum circuits for arbitrary sparse unitaries
Stephen P. Jordan, Pawel Wocjan
Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
Thomas Decker, Pawel Wocjan
New measures of graph irregularity
Clive Elphick, Pawel Wocjan
Estimating Jones and HOMFLY polynomials with One Clean Qubit
Stephen P. Jordan, Pawel Wocjan
Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices
Pawel Wocjan, Dominik Janzing, Thomas Beth
Identity check is QMA-complete
Dominik Janzing, Pawel Wocjan, Thomas Beth
Real Mutually Unbiased Bases
P. Oscar Boykin, Meera Sitharam, Mohamad Tarifi +1
Hamiltonian Quantum Cellular Automata in 1D
Daniel Nagaj, Pawel Wocjan
Fast Amplification of QMA
Daniel Nagaj, Pawel Wocjan, Yong Zhang
Recovering the Period in Shor's Algorithm with Gauss' Algorithm for Lattice Basis Reduction
Allison Koenecke, Pawel Wocjan
Estimating mixing properties of local Hamiltonian dynamics and continuous quantum random walks is PSPACE-hard
Pawel Wocjan
Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete
Dominik Janzing, Pawel Wocjan
On independent permutation separability criteria
Lieven Clarisse, Pawel Wocjan
Quantum Algorithms for One-Dimensional Infrastructures
Pradeep Sarvepalli, Pawel Wocjan
Mutually Unbiased Bases and Orthogonal Decompositions of Lie Algebras
P. Oscar Boykin, Meera Sitharam, Pham Huu Tiep +1
Characterization of combinatorially independent permutation separability criteria
Pawel Wocjan, Michal Horodecki
Required sample size for learning sparse Bayesian networks with many variables
Pawel Wocjan, Dominik Janzing, Thomas Beth
Hidden Symmetry Subgroup Problems
Thomas Decker, Gábor Ivanyos, Miklos Santha +1
Measuring 4-local n-qubit observables could probabilistically solve PSPACE
Pawel Wocjan, Dominik Janzing, Thomas Decker +1
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
A PromiseBQP-complete String Rewriting Problem
Dominik Janzing, Pawel Wocjan
The 2-local Hamiltonian problem encompasses NP
Pawel Wocjan, Thomas Beth
Bounds and power means for the general Randic index
Clive Elphick, Pawel Wocjan
On the Probability of Generating a Lattice
Felix Fontein, Pawel Wocjan
Testing quantum expanders is co-QMA-complete
Adam D. Bookatz, Stephen P. Jordan, Yi-Kai Liu +1
Conjectured bounds for the sum of squares of positive eigenvalues of a graph
Clive Elphick, Felix Goldberg, Miriam Farber +1
Treating the Independent Set Problem by 2D Ising Interactions with Adiabatic Quantum Computing
Pawel Wocjan, Dominik Janzing, Thomas Beth
Quantum Algorithm for Preparing Thermal Gibbs States - Detailed Analysis
Chen-Fu Chiang, Pawel Wocjan
Preparing ground states of quantum many-body systems on a quantum computer
David Poulin, Pawel Wocjan
Efficient Quantum Algorithm for Identifying Hidden Polynomials
Thomas Decker, Jan Draisma, Pawel Wocjan
Several natural BQP-Complete problems
Pawel Wocjan, Shengyu Zhang
An inertial lower bound for the chromatic number of a graph
Clive Elphick, Pawel Wocjan
Quantum Speed-up for Approximating Partition Functions
Pawel Wocjan, Chen-Fu Chiang, Anura Abeyesinghe +1
Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
Dominik Janzing, Pawel Wocjan, Thomas Beth
Two QCMA-complete problems
Pawel Wocjan, Dominik Janzing, Thomas Beth