Thermalizing quantum systems and evaluating partition functions with a quantum computer (2009)
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 a quantum system,...
Efficient quantum circuits for arbitrary sparse unitaries (2009)
Jordan, Stephen P., Wocjan, Pawel
Many existing quantum algorithms depend on efficient quantum circuits implementing sparse efficiently computable unitaries. These are unitary matrices of exponential dimension which have only...
Fast Amplification of QMA (2009)
Nagaj, Daniel, Wocjan, Pawel, Zhang, Yong
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 quadratically...
An Efficient Circuit for the Quantum Walk Update Rule (2009)
Chiang, Chen-Fu, Nagaj, Daniel, Wocjan, Pawel
We show how to efficiently implement quantum update rules corresponding to arbitrary sparse classical walks (Markov chains). These rules are required to realize quantum walks as defined by Szegedy....
Estimating Jones and HOMFLY polynomials with one clean qubit (2009)
Jordan, Stephen P., Wocjan, Pawel
The Jones and HOMFLY polynomials are link invariants with close connections to quantum computing. It was recently shown that finding a certain approximation to the Jones polynomial of the trace...
Quantum Algorithm for Identifying Hidden Polynomial Function Graphs (2008)
Thomas Decker, Jan Draisma, 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 graphs of linear...
Quantum Speed-up for Approximating Partition Functions (2008)
Wocjan, Pawel, Chiang, Chen-Fu, Abeyesinghe, Anura, Nagaj, Daniel
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 Markov Chain method...
Preparing ground states of quantum many-body systems on a quantum computer (2008)
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 exhaustively going through...
Janzing, Domink, Wocjan, Pawel, Zhang, Shengyu
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit...
Estimating Jones and HOMFLY polynomials with One Clean Qubit (2008)
Jordan, Stephen P., Wocjan, Pawel
The Jones and HOMFLY polynomials are link invariants with close connections to quantum computing. It was recently shown that finding a certain approximation to the Jones polynomial of the trace...
Speed-up via Quantum Sampling (2008)
Wocjan, Pawel, Abeyesinghe, Anura
The Markov Chain Monte Carlo method is at the heart of efficient approximation schemes for a wide range of problems in combinatorial enumeration and statistical physics. It is therefore very natural...
A simple PromiseBQP-complete matrix problem (2008)
Dominik Janzing, Pawel Wocjan, D. Janzing, P. Wocjan
Abstract: Let A be a real symmetric matrix of size N such that the number of non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an...
Hamiltonian Quantum Cellular Automata in 1D (2008)
We construct a simple translationally invariant, nearest-neighbor Hamiltonian on a chain of 10-dimensional qudits that makes it possible to realize universal quantum computing without any external...
Janzing, Dominik, Wocjan, Pawel, Zhang, Shenghui
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit...
Janzing, Dominik, Wocjan, Pawel, Zhang, Shengyu
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit...
Efficient Quantum Algorithm for Identifying Hidden Polynomials (2007)
Decker, Thomas, Draisma, Jan, Wocjan, Pawel
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 d elements. The...
A PromiseBQP-complete String Rewriting Problem (2007)
Janzing, Dominik, Wocjan, Pawel
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 constant length that...
Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs (2007)
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 graphs of linear...
BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs (2006)
Janzing, Dominik, Wocjan, Pawel
We describe two BQP-complete problems concerning properties of sparse graphs having a certain symmetry. The graphs are specified by efficiently computable functions which output the adjacent vertices...
Weak Fourier-Schur sampling, the hidden subgroup problem, and the quantum collision problem (2006)
Childs, Andrew M., Harrow, Aram W., Wocjan, Pawel
Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur...
Equivalence of Decoupling Schemes and Orthogonal Arrays (2006)
Rötteler, Martin, Wocjan, Pawel
Decoupling schemes are used in quantum information processing to selectively switch off unwanted interactions in a multipartite Hamiltonian. A decoupling scheme consists of a sequence of local...
Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete (2006)
Janzing, Dominik, Wocjan, Pawel
Let A be a real symmetric matrix of size N such that the number of the non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an...
Several natural BQP-Complete problems (2006)
A central problem in quantum computing is to identify computational tasks which can be solved substantially faster on a quantum computer than on any classical computer. By studying the hardest such...
Efficient decoupling schemes with bounded controls based on Eulerian orthogonal arrays (2006)
The task of decoupling, i.e., removing unwanted internal couplings of a quantum system and its couplings to an environment, plays an important role in quantum control theory. There are many efficient...
The Jones polynomial: quantum algorithms and applications in quantum complexity theory (2006)
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for...
On the quantum hardness of solving isomorphism problems as nonabelian hidden shift problems (2005)
Childs, Andrew M., Wocjan, Pawel
We consider an approach to deciding isomorphism of rigid n-vertex graphs (and related isomorphism problems) by solving a nonabelian hidden shift problem on a quantum computer using the standard...
Mutually Unbiased Bases and Orthogonal Decompositions of Lie Algebras (2005)
Boykin, P. Oscar, Sitharam, Meera, Tiep, Pham Huu, Wocjan, Pawel
We establish a connection between the problem of constructing maximal collections of mutually unbiased bases (MUBs) and an open problem in the theory of Lie algebras. More precisely, we show that a...
On independent permutation separability criteria (2005)
Clarisse, Lieven, Wocjan, Pawel
Recently P. Wocjan and M. Horodecki [quant-ph/0503129] gave a characterization of combinatorially independent permutation separability criteria. Combinatorial independence is a necessary condition...
Characterization of combinatorially independent permutation separability criteria (2005)
Wocjan, Pawel, Horodecki, Michal
The so-called permutation separability criteria are simple operational conditions that are necessary for separability of mixed states of multipartite systems: (1) permute the indices of the density...
Real Mutually Unbiased Bases (2005)
Boykin, P. Oscar, Sitharam, Meera, Tarifi, Mohamad, Wocjan, Pawel
We tabulate bounds on the optimal number of mutually unbiased bases in R^d. For most dimensions d, it can be shown with relatively simple methods that either there are no real orthonormal bases that...
The limitations of nice mutually unbiased bases (2004)
Aschbacher, Michael, Childs, Andrew M., Wocjan, Pawel
Mutually unbiased bases of a Hilbert space can be constructed by partitioning a unitary error basis. We consider this construction when the unitary error basis is a nice error basis. We show that the...
Efficient decoupling schemes with bounded controls based on Eulerian orthogonal arrays (2004)
The task of decoupling, i.e., removing unwanted interactions in a system Hamiltonian and/or couplings with an environment (decoherence), plays an important role in controlling quantum systems. There...
Equivalence of Decoupling Schemes and Orthogonal Arrays (2004)
Roetteler, Martin, Wocjan, Pawel
We consider the problem of switching off unwanted interactions in a given multi-partite Hamiltonian. This is known to be an important primitive in quantum information processing and several schemes...
New Construction of Mutually Unbiased Bases in Square Dimensions (2004)
We show that k=w+2 mutually unbiased bases can be constructed in any square dimension d=s^2 provided that there are w mutually orthogonal Latin squares of order s. The construction combines the...
Ergodic quantum computing (2004)
Janzing, Dominik, Wocjan, Pawel
We propose a (theoretical ;-) model for quantum computation where the result can be read out from the time average of the Hamiltonian dynamics of a 2-dimensional crystal on a cylinder. The...
A major topic of (classical) ergodic theory is to examine qualitatively how the phase space of dynamical systems is penetrated by the orbits of their dynamics. We consider interacting qubit systems...
Measuring 4-local n-qubit observables could probabilistically solve PSPACE (2003)
Wocjan, Pawel, Janzing, Dominik, Decker, Thomas, Beth, Thomas
We consider a hypothetical apparatus that implements measurements for arbitrary 4-local quantum observables A on n qubits. The apparatus implements the ``measurement algorithm'' after receiving a...
Two QCMA-complete problems (2003)
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
QMA and QCMA are possible quantum analogues of the complexity class NP. In QCMA the verifier is a quantum program and the proof is classical. In contrast, in QMA the proof is also a quantum state. We...
Identity check is QMA-complete (2003)
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
We define the problem identity check: Given a classical description of a quantum circuit, determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the...
Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete (2003)
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
We introduce the quantum complexity class FQMA. This class describes the complexity of generating a quantum state that serves as a witness for a given QMA problem. In a certain sense, FQMA is the...
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
We construct a nearest-neighbor Hamiltonian whose ground states encode the solutions to the NP-complete problem INDEPENDENT SET in cubic planar graphs. The Hamiltonian can be easily simulated by...
The 2-local Hamiltonian problem encompasses NP (2003)
We show that the NP complete problems MAX CUT and INDEPENDENT SET can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. He introduced the quantum complexity class BQNP as the...
Computational power of Hamiltonians in quantum computing / (2003)
Thesis (doctoral)--Technische Hochschule Karlsruhe, 2003.
Required sample size for learning sparse Bayesian networks with many variables (2002)
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
Learning joint probability distributions on n random variables requires exponential sample size in the generic case. Here we consider the case that a temporal (or causal) order of the variables is...
Bounds on the number of time steps for simulating arbitrary interaction graphs (2002)
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the...
Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices (2001)
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
A lower bound on the chromatic number of a graph is derived by majorization of spectra of weighted adjacency matrices. These matrices are given by Hadamard products of the adjacency matrix and...
Simulating Hamiltonians in Quantum Networks: Efficient Schemes and Complexity Bounds (2001)
Wocjan, Pawel, Roetteler, Martin, Janzing, Dominik, Beth, Thomas
We address the problem of simulating pair-interaction Hamiltonians in n node quantum networks where the subsystems have arbitrary, possibly different, dimensions. We show that any pair-interaction...
Universal Simulation of Hamiltonians Using a Finite Set of Control Operations (2001)
Wocjan, Pawel, Roetteler, Martin, Janzing, Dominik, Beth, Thomas
Any quantum system with a non-trivial Hamiltonian is able to simulate any other Hamiltonian evolution provided that a sufficiently large group of unitary control operations is available. We show that...
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
Well-known Nuclear Magnetic Resonance experiments show that the time evolution according to (truncated) dipole-dipole interactions between n spins can be inverted by simple pulse sequences....
Wocjan, Pawel, Lazic, Dejan E., Beth, Thomas
A conceptually simple method for derivation of lower bounds on the error exponent of specific families of block codes used on classical-quantum channels with arbitrary signal states over a finite...
Janzing, Dominik, Wocjan, Pawel, Zeier, Robert, Geiss, Rubino, Beth, Thomas
Landauer's principle states that the erasure of one bit of information requires the free energy kT ln 2. We argue that the reliability of the bit erasure process is bounded by the accuracy inherent...