arXiv:1004.2205

Quibbs, a Code Generator for Quantum Gibbs Sampling

Robert R. Tucci

Published Apr 11, 2010• 2 citations

Abstract

This paper introduces Quibbs v1.3, a Java application available for free. (Source code included in the distribution.) Quibbs is a "code generator" for quantum Gibbs sampling: after the user inputs some files that specify a classical Bayesian network, Quibbs outputs a quantum circuit for performing Gibbs sampling of that Bayesian network on a quantum computer. Quibbs implements an algorithm described in earlier papers, that combines various apple pie techniques such as: an adaptive fixed-point version of Grover's algorithm, Szegedy operators, quantum phase estimation and quantum multiplexors.

DOI: 10.48550/arxiv.1004.2205

Related papers

QOperAv, a Code Generator for Generating Quantum Circuits for Evaluating Certain Quantum Operator Averages

Robert R. Tucci

arXiv:1010.4926Oct 24, 20100 citations

Quantum Gibbs Sampling Using Szegedy Operators

Robert R. Tucci

arXiv:0910.1647Oct 9, 20094 citations

Code Generator for Quantum Simulated Annealing

Robert R. Tucci

arXiv:0908.1633Aug 12, 20097 citations

Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network

Robert R. Tucci

Importance sampling and Metropolis-Hastings sampling (of which Gibbs sampling is a special case) are two methods commonly used to sample multi-variate probability distributions (that is, Bayesian networks). Heretofore, the sampling of Bayesian networks has been done on a conventional "classical computer". In this paper, we propose methods for doing importance sampling and Metropolis-Hastings sampling of a classical Bayesian network on a quantum computer.

arXiv:0811.1792Nov 12, 20085 citations

QuanTree and QuanLin, Two Special Purpose Quantum Compilers

Robert R. Tucci

arXiv:0712.3887Dec 23, 20074 citations

Quantum inference on Bayesian networks

Guang Hao Low, Theodore J. Yoder, Isaac L. Chuang

arXiv:1402.7359Physical Review AJun 13, 2014109 citations

arXiv:1004.2205

Quibbs, a Code Generator for Quantum Gibbs Sampling

Robert R. Tucci

Published Apr 11, 2010• 2 citations

arXiv HTML PDF

Abstract

DOI: 10.48550/arxiv.1004.2205

Related papers

QOperAv, a Code Generator for Generating Quantum Circuits for Evaluating Certain Quantum Operator Averages

Robert R. Tucci

This paper introduces QOperAv v1.5, a Java application available for free. (Source code included in the distribution.) QOperAv is a "code generator" for generating quantum circuits. The quantum circuits generated by QOperAv can be used to evaluate with polynomial efficiency the average of $f(A)$ for some simple (that is, computable with polynomial efficiency) function $f$ and a Hermitian operator $A$ , provided that we know how to compile $\exp(iA)$ with polynomial efficiency. QOperAv implements an algorithm described in earlier papers, that combines various standard techniques such as quantum phase estimation and quantum multiplexors.This paper introduces QOperAv v1.5, a Java application available for free. (Source code included in the distribution.) QOperAv is a "code generator" for generating quantum circuits. The quantum circuits generated by QOperAv can be used to evaluate with polynomial efficiency the average of $f(A)$ for some simple (that is, computable with polynomial efficiency) function $f$ and a Hermitian operator $A$, provided that we know how to compile $\exp(iA)$ with polynomial efficiency. QOperAv implements an algorithm described in earlier papers, that combines various standard techniques such as quantum phase estimation and quantum multiplexors.

arXiv:1010.4926Oct 24, 20100 citations

Quantum Gibbs Sampling Using Szegedy Operators

Robert R. Tucci

We present an algorithm for doing Gibbs sampling on a quantum computer. The algorithm combines phase estimation for a Szegedy operator, and Grover's algorithm. For any $ε>0$ , the algorithm will sample a probability distribution in ${\cal O}(\frac{1}{\sqrtδ})$ steps with precision ${\cal O}(ε)$ . Here $δ$ is the distance between the two largest eigenvalue magnitudes of the transition matrix of the Gibbs Markov chain used in the algorithm. It takes ${\cal O}(\frac{1}δ)$ steps to achieve the same precision if one does Gibbs sampling on a classical computer.We present an algorithm for doing Gibbs sampling on a quantum computer. The algorithm combines phase estimation for a Szegedy operator, and Grover's algorithm. For any $ε>0$, the algorithm will sample a probability distribution in ${\cal O}(\frac{1}{\sqrtδ})$ steps with precision ${\cal O}(ε)$. Here $δ$ is the distance between the two largest eigenvalue magnitudes of the transition matrix of the Gibbs Markov chain used in the algorithm. It takes ${\cal O}(\frac{1}δ)$ steps to achieve the same precision if one does Gibbs sampling on a classical computer.

arXiv:0910.1647Oct 9, 20094 citations

Code Generator for Quantum Simulated Annealing

Robert R. Tucci

This paper introduces QuSAnn v1.2 and Multiplexor Expander v1.2, two Java applications available for free. (Source code included in the distribution.) QuSAnn is a "code generator" for quantum simulated annealing: after the user inputs some parameters, it outputs a quantum circuit for performing simulated annealing on a quantum computer. The quantum circuit implements the algorithm of Wocjan et al. (arXiv:0804.4259), which improves on the original algorithm of Somma et al. (arXiv:0712.1008). The quantum circuit generated by QuSAnn includes some quantum multiplexors. The application Multiplexor Expander allows the user to replace each of those multiplexors by a sequence of more elementary gates such as multiply controlled NOTs and qubit rotations.This paper introduces QuSAnn v1.2 and Multiplexor Expander v1.2, two Java applications available for free. (Source code included in the distribution.) QuSAnn is a "code generator" for quantum simulated annealing: after the user inputs some parameters, it outputs a quantum circuit for performing simulated annealing on a quantum computer. The quantum circuit implements the algorithm of Wocjan et al. (arXiv:0804.4259), which improves on the original algorithm of Somma et al. (arXiv:0712.1008). The quantum circuit generated by QuSAnn includes some quantum multiplexors. The application Multiplexor Expander allows the user to replace each of those multiplexors by a sequence of more elementary gates such as multiply controlled NOTs and qubit rotations.

arXiv:0908.1633Aug 12, 20097 citations

Use of a Quantum Computer to do Importance and Metropolis-Hastings Sampling of a Classical Bayesian Network

Robert R. Tucci

arXiv:0811.1792Nov 12, 20085 citations

QuanTree and QuanLin, Two Special Purpose Quantum Compilers

Robert R. Tucci

This paper introduces QuanTree v1.1 and QuanLin v1.1, two Java applications available for free. (Source code included in the distribution.) Each application compiles a different type of input quantum evolution operator. The applications output a quantum circuit that is approximately equal to the input evolution operator. QuanTree compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a balanced, binary tree graph. QuanLin compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a line (open string) graph. Both applications also output an error, defined as the distance in the Frobenius norm between the input evolution operator and the output quantum circuit.This paper introduces QuanTree v1.1 and QuanLin v1.1, two Java applications available for free. (Source code included in the distribution.) Each application compiles a different type of input quantum evolution operator. The applications output a quantum circuit that is approximately equal to the input evolution operator. QuanTree compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a balanced, binary tree graph. QuanLin compiles an input evolution operator whose Hamiltonian is proportional to the incidence matrix of a line (open string) graph. Both applications also output an error, defined as the distance in the Frobenius norm between the input evolution operator and the output quantum circuit.

arXiv:0712.3887Dec 23, 20074 citations

Quantum inference on Bayesian networks

Guang Hao Low, Theodore J. Yoder, Isaac L. Chuang

Performing exact inference on Bayesian networks is known to be $#P$-hard. Typically approximate inference techniques are used instead to sample from the distribution on query variables given the values $e$ of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on $n$ variables with at most $m$ parents per node in time $O(nmP{(e)}^{\ensuremath{-}1})$, depending critically on $P(e)$ , the probability that the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $O(n{2}^{m}P{(e)}^{\ensuremath{-}\frac{1}{2}})$ time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized---we count primitive operations and require no blackbox oracle queries.Performing exact inference on Bayesian networks is known to be $#P$-hard. Typically approximate inference techniques are used instead to sample from the distribution on query variables given the values $e$ of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on $n$ variables with at most $m$ parents per node in time $O(nmP{(e)}^{\ensuremath{-}1})$, depending critically on $P(e)$, the probability that the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $O(n{2}^{m}P{(e)}^{\ensuremath{-}\frac{1}{2}})$ time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized---we count primitive operations and require no blackbox oracle queries.

arXiv:1402.7359Physical Review AJun 13, 2014109 citations

f(A)

for some simple (that is, computable with polynomial efficiency) function

f

and a Hermitian operator

A

, provided that we know how to compile

\exp(iA)

with polynomial efficiency. QOperAv implements an algorithm described in earlier papers, that combines various standard techniques such as quantum phase estimation and quantum multiplexors.

We present an algorithm for doing Gibbs sampling on a quantum computer. The algorithm combines phase estimation for a Szegedy operator, and Grover's algorithm. For any

ε>0

, the algorithm will sample a probability distribution in

{\cal O}(\frac{1}{\sqrtδ})

steps with precision

{\cal O}(ε)

. Here

δ

is the distance between the two largest eigenvalue magnitudes of the transition matrix of the Gibbs Markov chain used in the algorithm. It takes

{\cal O}(\frac{1}δ)

steps to achieve the same precision if one does Gibbs sampling on a classical computer.

e

of evidence variables. Classically, a single unbiased sample is obtained from a Bayesian network on

n

variables with at most

m

parents per node in time $O(nmP{(e)}^{\ensuremath{-}1})$, depending critically on

P(e)

, the probability that the evidence might occur in the first place. By implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $O(n{2}^{m}P{(e)}^{\ensuremath{-}\frac{1}{2}})$ time per sample. We exploit the Bayesian network's graph structure to efficiently construct a quantum state, a q-sample, representing the intended classical distribution, and also to efficiently apply amplitude amplification, the source of our speedup. Thus, our speedup is notable as it is unrelativized---we count primitive operations and require no blackbox oracle queries.