Source author record

Pawel Wocjan

Pawel Wocjan appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

26works
8topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

26 published item(s)

preprint2022arXiv

Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions

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 modify the classical algorithm of Štefankovič, Vempala and Vigoda (\emph{J.~ACM}, 56(3), 2009) to improve its sample complexity; second, we quantize this new algorithm, improving upon the previously fastest quantum algorithm for this problem, due to Harrow and Wei (SODA 2020). The conventional approach to estimating partition functions requires approximating the means of Gibbs distributions at a set of inverse temperatures that form the so-called cooling schedule. The length of the cooling schedule directly affects the complexity of the algorithm. Combining our improved version of the algorithm of Štefankovič, Vempala and Vigoda with the paired-product estimator of Huber (\emph{Ann.\ Appl.\ Probab.}, 25(2),~2015), our new quantum algorithm uses a shorter cooling schedule than previously known. This length matches the optimal length conjectured by Štefankovič, Vempala and Vigoda. The quantum algorithm also achieves a quadratic advantage in the number of required quantum samples compared to the number of random samples drawn by the best classical algorithm, and its computational complexity has quadratically better dependence on the spectral gap of the Markov chains used to produce the quantum samples.

preprint2022arXiv

Space-efficient Quantization Method for Reversible Markov Chains

In a seminal paper, Szegedy showed how to construct a quantum walk $W(P)$ for any reversible Markov chain $P$ such that its eigenvector with eigenphase $0$ is a quantum sample of the limiting distribution of the random walk and its eigenphase gap is quadratically larger than the spectral gap of $P$. The standard construction of Szegedy's quantum walk requires an ancilla register of Hilbert-space dimension equal to the size of the state space of the Markov chain. We show that it is possible to avoid this doubling of state space for certain Markov chains that employ a symmetric proposal probability and a subsequent accept/reject probability to sample from the Gibbs distribution. For such Markov chains, we give a quantization method which requires an ancilla register of dimension equal to only the number of different energy values, which is often significantly smaller than the size of the state space. To accomplish this, we develop a technique for block encoding Hadamard products of matrices which may be of wider interest.

preprint2020arXiv

More Tales of Hoffman: bounds for the vector chromatic number of a graph

Let $χ(G)$ denote the chromatic number of a graph and $χ_v(G)$ denote the vector chromatic number. For all graphs $χ_v(G) \le χ(G)$ and for some graphs $χ_v(G) \ll χ(G)$. Galtman proved that Hoffman's well-known lower bound for $χ(G)$ is in fact a lower bound for $χ_v(G)$. We prove that two more spectral lower bounds for $χ(G)$ are also lower bounds for $χ_v(G)$. We then use one of these bounds to derive a new characterization of $χ_v(G)$.

preprint2016arXiv

Improved bounded-strength decoupling schemes for local Hamiltonians

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 bounded-strength controls, for quantum many-body systems with local system Hamiltonians and local environmental couplings. To do so, we introduce the combinatorial concept of balanced-cycle orthogonal arrays (BOAs) and show how to construct them from classical error-correcting codes. The derived decoupling schemes may be useful as a primitive for more complex schemes, e.g., for Hamiltonian simulation. For the case of $n$ qubits and a $2$-local Hamiltonian, the length of the resulting decoupling scheme scales as $O(n \log n)$, improving over the previously best-known schemes that scaled quadratically with $n$. More generally, using balanced-cycle orthogonal arrays constructed from families of BCH codes, we show that bounded-strength decoupling for any $\ell$-local Hamiltonian, where $\ell \geq 2$, can be achieved using decoupling schemes of length at most $O(n^{\ell-1} \log n)$.

preprint2015arXiv

Bounds and power means for the general Randic index

We review bounds for the general Randić index, $R_α = \sum_{ij \in E} (d_i d_j)^α$, and use the power mean inequality to prove, for example, that $R_α\ge mλ^{2α}$ for $α< 0$, where $λ$ is the spectral radius of a graph. This enables us to strengthen various known lower and upper bounds for $R_α$ and to generalise a non-spectral bound due to Bollobás \emph{et al}. We also prove that the zeroth-order general Randić index, $Q_α= \sum_{i \in V} d_i^α\ge nλ^α$ for $α< 0$.

preprint2015arXiv

Conjectured bounds for the sum of squares of positive eigenvalues of a graph

A well known upper bound for the spectral radius of a graph, due to Hong, is that $μ_1^2 \le 2m - n + 1$. It is conjectured that for connected graphs $n - 1 \le s^+ \le 2m - n + 1$, where $s^+$ denotes the sum of the squares of the positive eigenvalues. The conjecture is proved for various classes of graphs, including bipartite, regular, complete $q$-partite, hyper-energetic, and barbell graphs. Various searches have found no counter-examples. The paper concludes with a brief discussion of the apparent difficulties of proving the conjecture in general.

preprint2014arXiv

New measures of graph irregularity

In this paper, we define and compare four new measures of graph irregularity. We use these measures to prove upper bounds for the chromatic number and the Colin de Verdiere parameter. We also strengthen the concise Turan theorem for irregular graphs and investigate to what extent Turan's theorem can be similarly strengthened for generalized r-partite graphs. We conclude by relating these new measures to the Randic index and using the measures to devise new normalised indices of network heterogeneity.

preprint2014arXiv

Unified spectral bounds on the chromatic number

One of the best known results in spectral graph theory is the following lower bound on the chromatic number due to Alan Hoffman, where mu_1 and mu_n are respectively the maximum and minimum eigenvalues of the adjacency matrix: chi >= 1 + mu_1 / (- mu_n). We recently generalised this bound to include all eigenvalues of the adjacency matrix. In this paper, we further generalize these results to include all eigenvalues of the adjacency, Laplacian and signless Laplacian matrices. The various known bounds are also unified by considering the normalized adjacency matrix, and examples are cited for which the new bounds outperform known bounds.

preprint2013arXiv

Hamiltonian quantum simulation with bounded-strength controls

We propose dynamical control schemes for Hamiltonian simulation in many-body quantum systems that avoid instantaneous control operations and rely solely on realistic bounded-strength control Hamiltonians. Each simulation protocol consists of periodic repetitions of a basic control block, constructed as a suitable modification of an "Eulerian decoupling cycle," that would otherwise implement a trivial (zero) target Hamiltonian. For an open quantum system coupled to an uncontrollable environment, our approach may be employed to engineer an effective evolution that simulates a target Hamiltonian on the system, while suppressing unwanted decoherence to the leading order. We present illustrative applications to both closed- and open-system simulation settings, with emphasis on simulation of non-local (two-body) Hamiltonians using only local (one-body) controls. In particular, we provide simulation schemes applicable to Heisenberg-coupled spin chains exposed to general linear decoherence, and show how to simulate Kitaev's honeycomb lattice Hamiltonian starting from Ising-coupled qubits, as potentially relevant to the dynamical generation of a topologically protected quantum memory. Additional implications for quantum information processing are discussed.

preprint2013arXiv

On the Probability of Generating a Lattice

We study the problem of determining the probability that m vectors selected uniformly at random from the intersection of the full-rank lattice L in R^n and the window [0,B)^n generate $Λ$ when B is chosen to be appropriately large. This problem plays an important role in the analysis of the success probability of quantum algorithms for solving the Discrete Logarithm Problem in infrastructures obtained from number fields and also for computing fundamental units of number fields. We provide the first complete and rigorous proof that 2n+1 vectors suffice to generate L with constant probability (provided that B is chosen to be sufficiently large in terms of n and the covering radius of L and the last n+1 vectors are sampled from a slightly larger window). Based on extensive computer simulations, we conjecture that only n+1 vectors sampled from one window suffice to generate L with constant success probability. If this conjecture is true, then a significantly better success probability of the above quantum algorithms can be guaranteed.

preprint2013arXiv

Recovering the Period in Shor's Algorithm with Gauss' Algorithm for Lattice Basis Reduction

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 positive integer. Assume that with some constant probability we obtain random positive integers of the form x=[ N k/r ] where [.] is either the floor or ceiling of the rational number, k is selected uniformly at random from {0,1,...,r-1}, and N is a parameter that can be chosen. The problem of recovering r from such samples occurs precisely in the classical post-processing part of Shor's algorithm. The quantum part (quantum phase estimation) makes it possible to obtain such samples where r is the order of some element a of the unit group of Z_n and n is the number to be factored. Shor showed that the continued fraction algorithm can be used to efficiently recover r, since if N>2r^2 then k/r appears in lowest terms as one of the convergents of x/N due to a standard result on continued fractions. We present here an alternative method for recovering r based on the Gauss algorithm for lattice basis reduction, allowing us to efficiently find the shortest nonzero vector of a lattice generated by two vectors. Our method is about as efficient as the method based on continued fractions, yet it is much easier to understand all the details of why it works.

preprint2013arXiv

Testing quantum expanders is co-QMA-complete

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 problem of estimating the mixing time (i.e., the spectral gap) of a quantum expander. We show that this problem is co-QMA-complete. This has applications to testing randomized constructions of quantum expanders, and studying thermalization of open quantum systems.

preprint2012arXiv

Efficient Computation of the Permanent of Block Factorizable Matrices

We present an efficient algorithm for computing the permanent for matrices of size N that can written as a product of L block diagonal matrices with blocks of size at most 2. For fixed L, the time and space resources scale linearly in N, with a prefactor that scales exponentially in L. This class of matrices contains banded matrices with banded inverse. We show that such a factorization into a product of block diagonal matrices gives rise to a circuit acting on a Hilbert space with a tensor product structure and that the permanent is equal to the transition amplitude of this circuit and a product basis state. In this correspondence, a block diagonal matrix gives rise to one layer of the circuit, where each block to a gate acting either on a single tensor component or on two adjacent tensor components. This observation allows us to adopt matrix product states, a computational method from condensed matter physics and quantum information theory used to simulate quantum systems, to evaluate the transition amplitude.

preprint2012arXiv

Hidden Symmetry Subgroup Problems

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), which is a generalization of the well-studied Hidden Subgroup Problem (HSP). Given a group acting on a set and an oracle whose level sets define a partition of the set, the task is to recover the subgroup of symmetries of this partition inside the group. The HSSP provides a unifying framework that, besides the HSP, encompasses a wide range of algebraic oracle problems, including quadratic hidden polynomial problems. While the HSSP can have provably exponential quantum query complexity, we obtain efficient quantum algorithms for various interesting cases. To achieve this, we present a general method for reducing the HSSP to the HSP, which works efficiently in several cases related to symmetries of polynomials. The HSSP therefore connects in a rather surprising way certain hidden polynomial problems with the HSP. Using this connection, we obtain the first efficient quantum algorithm for the hidden polynomial problem for multivariate quadratic polynomials over fields of constant characteristic. We also apply the new methods to polynomial function graph problems and present an efficient quantum procedure for constant degree multivariate polynomials over any field. This result improves in several ways the currently known algorithms.

preprint2012arXiv

New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix

The purpose of this article is to improve existing lower bounds on the chromatic number chi. Let mu_1,...,mu_n be the eigenvalues of the adjacency matrix sorted in non-increasing order. First, we prove the lower bound chi >= 1 + max_m {sum_{i=1}^m mu_i / - sum_{i=1}^m mu_{n-i+1}} for m=1,...,n-1. This generalizes the Hoffman lower bound which only involves the maximum and minimum eigenvalues, i.e., the case $m=1$. We provide several examples for which the new bound exceeds the {\sc Hoffman} lower bound. Second, we conjecture the lower bound chi >= 1 + S^+ / S^-, where S^+ and S^- are the sums of the squares of positive and negative eigenvalues, respectively. To corroborate this conjecture, we prove the weaker bound chi >= S^+/S^-. We show that the conjectured lower bound is tight for several families of graphs. We also performed various searches for a counter-example, but none was found. Our proofs rely on a new technique of converting the adjacency matrix into the zero matrix by conjugating with unitary matrices and use majorization of spectra of self-adjoint matrices. We also show that the above bounds are actually lower bounds on the normalized orthogonal rank of a graph, which is always less than or equal to the chromatic number. The normalized orthogonal rank is the minimum dimension making it possible to assign vectors with entries of modulus one to the vertices such that two such vectors are orthogonal if the corresponding vertices are connected. All these bounds are also valid when we replace the adjacency matrix A by W * A where W is an arbitrary self-adjoint matrix and * denotes the Schur product, that is, entrywise product of W and A.

preprint2012arXiv

Quantum Algorithms for One-Dimensional Infrastructures

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 finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.

preprint2010arXiv

Efficient quantum circuits for arbitrary sparse unitaries

Arbitrary exponentially large unitaries cannot be implemented efficiently by quantum circuits. However, we show that quantum circuits can efficiently implement any unitary provided it has at most polynomially many nonzero entries in any row or column, and these entries are efficiently computable. One can formulate a model of computation based on the composition of sparse unitaries which includes the quantum Turing machine model, the quantum circuit model, anyonic models, permutational quantum computation, and discrete time quantum walks as special cases. Thus we obtain a simple unified proof that these models are all contained in BQP. Furthermore our general method for implementing sparse unitaries simplifies several existing quantum algorithms.

preprint2010arXiv

Quantum Algorithm for Preparing Thermal Gibbs States - Detailed Analysis

In a recent work [10], Poulin and one of us presented a quantum algorithm for preparing thermal Gibbs states of interacting quantum systems. This algorithm is based on Grovers's technique for quantum state engineering, and its running time is dominated by the factor D/Z(β), where D and Z(β) denote the dimension of the quantum system and its partition function at inverse temperature β, respectively. We present here a modified algorithm and a more detailed analysis of the errors that arise due to imperfect simulation of Hamiltonian time evolutions and limited performance of phase estimation (finite accuracy and nonzero probability of failure). This modfication together with the tighter analysis allows us to prove a better running time by the effect of these sources of error on the overall complexity. We think that the ideas underlying of our new analysis could also be used to prove a better performance of quantum Metropolis sampling by Temme et al. [12].

preprint2009arXiv

Efficient Circuits for Quantum Walks

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's method for preparing coherent versions of efficiently integrable probability distributions. This method is intended for use in quantum walk algorithms with polynomial speedups, whose complexity is usually measured in terms of how many times we have to apply a step of a quantum walk, compared to the number of necessary classical Markov chain steps. We consider a finer notion of complexity including the number of elementary gates it takes to implement each step of the quantum walk with some desired accuracy. The difference in complexity for various implementation approaches is that our method scales linearly in the sparsity parameter and poly-logarithmically with the inverse of the desired precision. The best previously known general methods either scale quadratically in the sparsity parameter, or polynomially in the inverse precision. Our approach is especially relevant for implementing quantum walks corresponding to classical random walks like those used in the classical algorithms for approximating permanents and sampling from binary contingency tables. In those algorithms, the sparsity parameter grows with the problem size, while maintaining high precision is required.

preprint2009arXiv

Quantum Speed-up for Approximating Partition Functions

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 and use non-adaptive cooling schedules. The improvement in time complexity is twofold: a quadratic reduction with respect to the spectral gap of the underlying Markov chains and a quadratic reduction with respect to the parameter characterizing the desired accuracy of the estimate output by the FPRAS. Both reductions are intimately related and cannot be achieved separately. First, we use Grover's fixed point search, quantum walks and phase estimation to efficiently prepare approximate coherent encodings of stationary distributions of the Markov chains. The speed-up we obtain in this way is due to the quadratic relation between the spectral and phase gaps of classical and quantum walks. Second, we generalize the method of quantum counting, showing how to estimate expected values of quantum observables. Using this method instead of classical sampling, we obtain the speed-up with respect to accuracy.

preprint2009arXiv

Sampling from the thermal quantum Gibbs state and evaluating partition functions with a quantum computer

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, where D is the system's Hilbert space dimension and alpha < 1/2 is proportional to the Helmholtz free energy density of the system. We also derive an algorithm to evaluate the partition function of a quantum system in a time proportional to the system's thermalization time and inversely proportional to the targeted accuracy squared.

preprint2008arXiv

Estimating Jones and HOMFLY polynomials with One Clean Qubit

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 closure of a braid at the fifth root of unity is a complete problem for the one clean qubit complexity class. This is the class of problems solvable in polynomial time on a quantum computer acting on an initial state in which one qubit is pure and the rest are maximally mixed. Here we generalize this result by showing that one clean qubit computers can efficiently approximate the Jones and single-variable HOMFLY polynomials of the trace closure of a braid at any root of unity.

preprint2008arXiv

Preparing ground states of quantum many-body systems on a quantum computer

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 all N configurations of the system to determine the one with lowest energy, requiring a running time proportional to N. A quantum computer, if it could be built, could solve this problem in time sqrt(N). Here, we present a powerful extension of this result to the case of interacting quantum particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.

preprint2007arXiv

The Jones polynomial: quantum algorithms and applications in quantum complexity theory

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 implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al. that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a #P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.

preprint2004arXiv

Efficient decoupling schemes with bounded controls based on Eulerian orthogonal arrays

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 are many efficient decoupling schemes based on combinatorial concepts like orthogonal arrays, difference schemes and Hadamard matrices. So far these (combinatorial) decoupling schemes have relied on the ability to effect sequences of instantaneous, arbitrarily strong control Hamiltonians (bang-bang controls). To overcome the shortcomings of bang-bang control Viola and Knill proposed a method called Eulerian decoupling that allows the use of bounded-strength controls for decoupling. However, their method was not directly designed to take advantage of the composite structure of multipartite quantum systems. In this paper we define a combinatorial structure called an Eulerian orthogonal array. It merges the desirable properties of orthogonal arrays and Eulerian cycles in Cayley graphs (that are the basis of Eulerian decoupling). We show that this structure gives rise to decoupling schemes with bounded-strength control Hamiltonians that can be applied to composite quantum systems with few body Hamiltonians and special couplings with the environment. Furthermore, we show how to construct Eulerian orthogonal arrays having good parameters in order to obtain efficient decoupling schemes.

preprint2003arXiv

Identity check is QMA-complete

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 corresponding unitary is close to a complex multiple of the identity matrix with respect to the operator norm. We show that this problem is QMA-complete. A generalization of this problem is equivalence check: Given two descriptions of quantum circuits and a description of a common invariant subspace, decide whether the restrictions of the circuits to this subspace almost coincide. We show that equivalence check is also in QMA and hence QMA-complete.