# US 8,543,627 B1 · Method for sampling probability distributions using a quantum computer > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,627 B1 - Document ID: US8543627B1 - Status: Granted - Kind: B1 - Application number: 12/924,654 - Filed: 2010-10-01 - Granted: 2013-09-24 - Earliest claimed: 2010-10-01 - Applicants: Robert R. Tucci - Inventors: Robert R. Tucci - Web page: https://patentgrep.com/patent/US8543627B1 ## CPC - G06N 10/80: Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing - B82Y 10/00: Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic - G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - B82Y: SPECIFIC USES OR APPLICATIONS OF NANOSTRUCTURES; MEASUREMENT OR ANALYSIS OF NANOSTRUCTURES; MANUFACTURE OR TREATMENT OF NANOSTRUCTURES ## Abstract We describe a method for using a classical computer to generate a sequence of elementary operation (SEO) that can be used to operate a quantum computer, thereby inducing the quantum computer to sample an arbitrary probability distribution. The probability distribution being sampled is specified in the form of a Bayesian network. ## Claims ### Claim 1 A method of operating a classical computer to calculate a total SEO, with the purpose of using said total SEO to operate a quantum computer, and to induce said quantum computer to approximately sample a probability distribution π(x) defined for all x∈{0,1}NB, said method comprising the steps of: storing in said classical computer a data trove comprising a positive number ε, a point x0∈{0,1}NB such that π(x0) is nonzero, and a data-set that specifies said probability distribution π(x), calculating using said classical computer and using said data trove, a sequence of unitary operators U0, U1, U2, . . . , UM, wherein M depends on ε, wherein there are unit vectors |Φ1 and |Φ2(x) such that if ERR=∥v1−|2|2 where |v1=UM . . . U1U0|x0|Φ1 and |v2=Σx√{square root over (π(x))}|x|Φ2(x), then ERR≦ε, calculating using said classical computer for each j=0,1,2, . . . M, a SEO Σj corresponding to Uj, wherein said total SEO equals the product ΣM . . . Σ1Σ0. ### Claim 2 (depends on 1) The method of claim 1, wherein said data trove comprises a net data-set that specifies a Bayesian network with full probability distribution equal to said π(x), wherein said net data-set comprises: (a) a data-set that characterizes the possible states of each node of said Bayesian network, (b) a data-set that characterizes the parent nodes of each node of said Bayesian network, (c) a data-set that characterizes a multiplicity of conditional probabilities associated with each node of said Bayesian network. ### Claim 3 (depends on 1) The method of claim 1, wherein if A is the subset of {0,1,2, . . . M} such that for all j in A, Uj has only two distinct eigenvalues λ1j and λ2j such that the product λijλ2j* is not in the set {eiπ/3,e−iπ/3,−1}, then A has 3 or more elements. ### Claim 4 (depends on 3) The method of claim 3, wherein A has about M elements. ### Claim 5 (depends on 1) The method of claim 1, wherein for each j=0,1,2, . . . M, said SEO Σj has a number of elementary operations that scales polynomially in NB. ### Claim 6 (depends on 1) The method of claim 1, further utilizing a quantum computer, comprising the additional step of: operating said quantum computer according to said total SEO. ### Claim 7 (depends on 1) The method of claim 1, wherein said sequence of unitary operators U0,U1, . . . UM alternates between unitary operators that have |x|α for some state |α, as an approximate eigenvector, and unitary operators that have Σx√{square root over (π(x))}|x|β for some state |β, as an approximate eigenvector. ### Claim 8 A device that calculates a total SEO, with the purpose of using said total SEO to operate a quantum computer, and to induce said quantum computer to approximately sample a probability distribution π(x) defined for all x∈{0,1}NB, said device comprising: a memory arranged to store a data trove comprising a positive number ε, a point x0∈{0,1}NB such that π(x0) is nonzero, and a data-set that specifies said probability distribution π(x), a processor arranged to calculate using said data trove stored in said memory, a sequence of unitary operators U0,U1,U2, . . . ,UM, wherein M depends on ε, and arranged to calculate for each j=0,1,2, . . . M, a SEO Σj corresponding to Uj, wherein there are unit vectors |Φ1 and |Φ2(x) such that if ERR=∥v1−|v2|2 where |v1=UM . . . U1U0|x0|Φ1 and |v2=Σx√{square root over (π(x))}|x|Φ2(x), then ERR≦ε, wherein said total SEO equals the product ΣM . . . Σ1Σ0. ### Claim 9 (depends on 8) The device of claim 8, wherein said data trove comprises a net data-set that specifies a Bayesian network with full probability distribution equal to said π(x), wherein said net data-set comprises: (a) a data-set that characterizes the possible states of each node of said Bayesian network, (b) a data-set that characterizes the parent nodes of each node of said Bayesian network, (c) a data-set that characterizes a multiplicity of conditonal probabilities associated with each node of said Bayesian network. ### Claim 10 (depends on 8) The device of claim 8, wherein if A is the subset of {0,1,2, . . . M} such that for all j in A, Uj has only two distinct eigenvalues λ1j and λ2j such that the product λ1jλ2j8 is not in the set {eiπ/3,e−iπ/3,−1}, then A has 3 or more elements. ### Claim 11 (depends on 10) The device of claim 10, wherein A has about M elements. ### Claim 12 (depends on 8) The device of claim 8, further comprising a quantum computer that operates according to said total SEO. ### Claim 13 (depends on 8) The device of claim 8, wherein said sequence of unitary operators U0,U1, . . . UM alternates between unitary operators that have |x|α for some state |α, as an approximate eigenvector, and unitary operators that have Σx√{square root over (π(x))}|x|β for some state |β, as an approximate eigenvector. ### Claim 14 A method of operating a classical computer to calculate a total SEO, with the purpose of using said total SEO to operate a quantum computer, and to induce said quantum computer to approximately sample a probability distribution π(x) defined for all x∈{0,1}NB, said method comprising the steps of: storing in said classical computer a data trove comprising a positive number ε, and a data-set that specifies a multiplicity of conditional probabilities of said π(x), calculating using said classical computer and using said data trove, a sequence of unitary operators U0,U1,U2, . . . , UM, wherein M depends on ε, wherein there are unit vectors |Φ1 and |Φ2(x) such that if ERR=∥v1−|v2|2 where |v1=UM . . . U1U0|Φ1 and |v2=Σx√{square root over (π(x))}|x|Φ2(x), then ERR≦ε, calculating using said classical computer for each j=0,1,2, . . . M, a SEO Σj corresponding to Uj, wherein said total SEO equals the product ΣM . . . . Σ1Σ0. ### Claim 15 (depends on 14) The method of claim 14, wherein if A is the subset of {0,1,2, . . . M} such that for all j in A, Uj has only two distinct eigenvalues λ1j and λ2j such that the product λ1jλ2j* is not in the set {eiπ/3,e−iπ/3,−1}, then A has 3 or more elements. ### Claim 16 (depends on 15) The method of claim 15, wherein A has about M elements. ### Claim 17 (depends on 14) The method of claim 14, wherein for each j=0,1,2, . . . M, said SEO Σj has a number of elementary operations that scales polynomially in NB. ### Claim 18 (depends on 14) The method of claim 14, further utilizing a quantum computer, comprising the additional step of: operating said quantum computer according to said total SEO. ### Claim 19 (depends on 14) The method of claim 14, wherein said sequence of unitary operators U0,U1, . . . UM alternates between unitary operators that have |x|α for some state |α, as an approximate eigenvector, and unitary operators that have Σx√{square root over (π(x))}|x|β for some state |β, as an approximate eigenvector. ### Claim 20 A device that calculates a total SEO, with the purpose of using said total SEO to operate a quantum computer, and to induce said quantum computer to approximately sample a probability distribution π(x) defined for all x∈{0,1}NB said device comprising: a memory arranged to store a data trove comprising a positive number ε, and a data-set that specifies a multiplicity of conditional probabilities of said π(x), a processor arranged to calculate using said data trove stored in said memory, a sequence of unitary operators U0,U1,U2, . . . , UM, wherein M depends on ε, and arranged to calculate for each j=0,1,2, . . . M, a SEO Σj corresponding to Uj, wherein said total SEO equals the product ΣM . . . Σ1Σ0, wherein there are unit vectors |Φ1 and |Φ2(x) such that if ERR=∥v1−|v2|2 where |v1=UM . . . U1U0|Φ1 and |v2=Σx√{square root over (π(x))}|x|Φ2(x), then ERR≦ε. ### Claim 21 (depends on 20) The device of claim 20, wherein if A is the subset of {0,1,2, . . . M} such that for all j in A, Uj has only two distinct eigenvalues λ1j and λ2j such that the product λ1jλ2j* is not in the set {eiπ/3,e−iπ/3,−1}, then A has 3 or more elements. ### Claim 22 (depends on 21) The device of claim 21, wherein A has about M elements. ### Claim 23 (depends on 20) The device of claim 20, wherein for each j=0,1,2, . . . M, said SEO Σj has a number of elementary operations that scales polynomially in NB. ### Claim 24 (depends on 20) The device of claim 20, further comprising a quantum computer that operates according to said total SEO. ### Claim 25 (depends on 20) The device of claim 20, wherein said sequence of unitary operators U0,U1, . . . UM alternates between unitary operators that have |x|α for some state |α, as an approximate eigenvector, and unitary operators that have Σx√{square root over (π(x))}|x|β for some state |β, as an approximate eigenvector.