Solution to the Sign Problem Using a Sum of Controlled Few-Fermions

Abstract

Methods and systems of Monte Carlo quantum computing are disclosed for simulating quantum systems and implementing quantum computing efficiently on a classical computer, including methods and systems for simulating many-variable signed densities, methods and systems for decomposing a many-variable density into a combination of few-variable signed densities, and methods and systems for solving a computational problem via Monte Carlo quantum computing.

What is claimed is: 
     
         1 . A method of simulating a many-variable (MV) signed density associated with an MV configuration space, said MV configuration space being a set of MV configuration points each of which is represented by a tuple or vector of variable values assigned to a first ensemble of coordinate variables, said first ensemble of coordinate variables consisting of a variable number N of members, said MV signed density being practically substantially entangled, said method comprising:
 providing a first means for decomposing said MV signed density into a combination of a first plurality K of few-variable (FV) signed densities, each of said FV signed densities corresponding to a second ensemble of coordinate variables selected from said first ensemble of coordinate variables, said corresponding second ensemble of coordinate variables consisting of a second plurality of members, wherein said first plurality is substantially upper-bounded by a first predetermined polynomial of said variable number N, said second plurality is substantially upper-bounded by a predetermined logarithm of a second predetermined polynomial of said variable number N;   providing a second means for determining FV nodal surfaces corresponding to each of said FV signed densities, each of said FV nodal surfaces enclosing a corresponding FV nodal cell in which the corresponding FV signed density is non-negative-valued, said corresponding FV nodal cell being a corresponding subset of said MV configuration space, each pair of MV configuration points in said corresponding subset differing from each other at most in variable values assigned to coordinate variables selected from the corresponding second ensemble of coordinate variables;   providing a third means for producing a third plurality of samples of FV restricted densities, each of said FV restricted densities being substantially equal to a corresponding one of said FV signed densities restricted to one of the corresponding nodal cells, wherein said third plurality is substantially upper-bounded by a third predetermined polynomial of said variable number N, said samples of said FV restricted densities are non-negative-valued;   providing a fourth means for producing a fourth plurality of samples of an MV restricted density by combining said third plurality of samples of FV restricted densities, wherein said fourth plurality is substantially upper-bounded by a fourth predetermined polynomial of said variable number N, said samples of said MV restricted density are non-negative-valued;   whereby said MV restricted density is substantially equivalent to said MV signed density in the sense that a signed expectation value of a prescribed observable due to said MV restricted density is substantially equal to the signed expectation value of said prescribed observable due to said MV signed density, said prescribed observable is selected from the group consisting of the number 1, a predetermined constant, and a prescribed function associated with a subset of said MV configuration space.   
     
     
         2 . The method of  claim 1 , wherein said MV signed density has a severe sign problem. 
     
     
         3 . The method of  claim 1 , further comprising a fifth means for computing the signed expectation value of said prescribed observable due to said MV restricted density. 
     
     
         4 . The method of  claim 1 , wherein said MV signed density is associated with an MV symmetry group, said MV symmetry group induces an MV group action on said MV configuration space thereby permutes a first set of MV nodal cells corresponding to said MV signed density, each of said MV nodal cells tiles up said MV configuration space under said MV group action, each of said FV signed densities is associated with a corresponding FV symmetry group, said corresponding FV symmetry group has an order (namely, cardinality) that is substantially upper-bounded by a fifth predetermined polynomial of said variable number N, said corresponding FV symmetry group induces a corresponding FV group action on said MV configuration space thereby permutes a second set of FV nodal cells corresponding to the corresponding FV signed density, a collection of the corresponding FV symmetry groups associated with the FV signed densities generates said MV symmetry group. 
     
     
         5 . The method of  claim 1 , wherein said MV signed density is selected from the group consisting of ground state wavefunctions, Gibbs wavefunctions, Gibbs kernels, Gibbs transition amplitudes, and Wiener densities, said MV signed density is associated with a quantum system that is governed by a total Hamiltonian selected from the group consisting of strongly frustration-free Hamiltonians, ground sate frustration-free Hamiltonians, directly frustration-free Hamiltonians, separately frustration-free Hamiltonians, and sum-of-CFFs Hamiltonians. 
     
     
         6 . The method of  claim 5 , wherein said quantum system is a many-species fermionic system comprising a fifth plurality of fermion species, each of said fifth plurality of fermion species consists of a sixth plurality of identical fermions, said fifth plurality is substantially greater than aN α  for a predetermined pair of positive real numbers a and a, said sixth plurality is substantially less than a predetermined logarithm of bN β  for another predetermined pair of positive real numbers b and β, where N is said variable number. 
     
     
         7 . The method of  claim 5 , wherein said total Hamiltonian is substantially a Feynman-Kitaev Hamiltonian governing substantially a Feynman-Kitaev construct, said Feynman-Kitaev construct provides a means for spectral gap amplification such that the ground state and the excited states of said Feynman-Kitaev Hamiltonian is separated by an amplified spectral gap, said amplified spectral gap is substantially greater than cK −γ  for a predetermined pair of positive real numbers c and γ, where K is said first plurality, said positive real number γ is less than 2. 
     
     
         8 . A method of simulating a many-variable (MV) signed density, said MV signed density being induced by an MV transition operator, said MV transition operator involving a first ensemble of coordinate variables, said first ensemble of coordinate variables consisting of a variable number N of members, a tuple or vector of variable values assigned to said first ensemble of coordinate variables representing an MV configuration point, a set of such MV configuration points constituting an MV configuration space, said MV signed density being practically substantially entangled, said method comprising:
 providing a first means for decomposing said MV transition operator into a combination of a first plurality K of few-variable (FV) transition operators, each of said FV transition operators involving a corresponding second ensemble of coordinate variables selected from said first ensemble of coordinate variables, said corresponding second ensemble of coordinate variables consisting of a second plurality L of members, each of said FV transition operators inducing a corresponding one of FV signed densities, wherein said first plurality is substantially upper-bounded by a first predetermined polynomial of said variable number N, said second plurality L is substantially upper-bounded by a predetermined logarithm of a second predetermined polynomial of said variable number N;   providing a second means for determining FV nodal surfaces corresponding to each of said FV signed densities, each of said FV nodal surfaces enclosing a corresponding FV nodal cell in which the corresponding FV signed density is non-negative-valued, said corresponding FV nodal cell being a corresponding subset of said MV configuration space, each pair of MV configuration points in said corresponding subset differing from each other at most in variable values assigned to coordinate variables selected from the corresponding second ensemble of coordinate variables;   providing a third means for producing a third plurality of samples of FV restricted densities, each of said FV restricted densities being substantially equal to a corresponding one of said FV signed densities restricted to one of the corresponding nodal cells, wherein said third plurality is substantially upper-bounded by a third predetermined polynomial of said variable number N, said samples of said FV restricted densities are non-negative-valued;   providing a fourth means for producing a fourth plurality of samples of an MV restricted density by combining said third plurality of samples of FV restricted densities, wherein said fourth plurality is substantially upper-bounded by a fourth predetermined polynomial of said variable number N, said samples of said MV restricted density are non-negative-valued;   whereby said MV restricted density is substantially equivalent to said MV signed density in the sense that a signed expectation value of a prescribed observable due to said MV restricted density is substantially equal to the signed expectation value of said prescribed observable due to said MV signed density, said prescribed observable is selected from the group consisting of the number 1, a predetermined constant, and a prescribed function associated with a subset of said MV configuration space.   
     
     
         9 . The method of  claim 8 , wherein said MV signed density has a severe sign problem. 
     
     
         10 . The method of  claim 8 , further comprising a fifth means for computing the signed expectation value of said prescribed observable due to said MV restricted density. 
     
     
         11 . The method of  claim 8 , wherein said MV signed density is associated with an MV symmetry group, said MV symmetry group induces an MV group action on said MV configuration space thereby permutes a first set of MV nodal cells corresponding to said MV signed density, each of said MV nodal cells tiles up said MV configuration space under said MV group action, each of said FV signed densities is associated with a corresponding FV symmetry group, said corresponding FV symmetry group has an order (namely, cardinality) that is substantially upper-bounded by a fifth predetermined polynomial of said variable number N, said corresponding FV symmetry group induces a corresponding FV group action on said MV configuration space thereby permutes a second set of FV nodal cells corresponding to the corresponding FV signed density, a collection of the corresponding FV symmetry groups associated with the FV signed densities generates said MV symmetry group. 
     
     
         12 . The method of  claim 8 , wherein said MV signed density is selected from the group consisting of ground state wavefunctions, Gibbs wavefunctions, Gibbs kernels, Gibbs transition amplitudes, and Wiener densities, said MV signed density is associated with a quantum system, said MV transition operator is a Gibbs operator generated by a total Hamiltonian governing said quantum system, said total Hamiltonian is selected from the group consisting of strongly frustration-free Hamiltonians, ground sate frustration-free Hamiltonians, directly frustration-free Hamiltonians, separately frustration-free Hamiltonians, and sum-of-CFFs Hamiltonians. 
     
     
         13 . The method of  claim 12 , wherein said quantum system is a many-species fermionic system comprising a fifth plurality of fermion species, each of said fifth plurality of fermion species consists of a sixth plurality of identical fermions, said fifth plurality is substantially greater than aN α  for a predetermined pair of positive real numbers a and a, said sixth plurality is substantially less than a predetermined logarithm of bN β  for another predetermined pair of positive real numbers b and β, where N is said variable number. 
     
     
         14 . The method of  claim 12 , wherein said total Hamiltonian is substantially a Feynman-Kitaev Hamiltonian governing substantially a Feynman-Kitaev construct, said Feynman-Kitaev construct provides a means for spectral gap amplification such that the ground state and the excited states of said Feynman-Kitaev Hamiltonian is separated by an amplified spectral gap, said amplified spectral gap is substantially greater than cK −γ  for a predetermined pair of positive real numbers c and γ, where K is said first plurality, said positive real number γ is less than 2. 
     
     
         15 . A method of solving a computational problem, said computational problem being described by problem data, said method comprising:
 providing a first means for processing said problem data to produce Gibbs data, said first means comprising:
 providing a first processing means for producing circuit data describing a quantum circuit, said circuit data comprising qubit data and gate data, said qubit data comprising a description of a first plurality N b  of qubits, said gate data comprising a description of a second plurality N g  of quantum gates, wherein each of said quantum gates involves at most a first predetermined number of said qubits, said quantum circuit produces a quantum result encoding a solution to said computational problem; 
 providing a second processing means for producing homophysics data comprising coordinate data and Hamiltonian data, said coordinate data comprising a description of a first ensemble of coordinate variables, said first ensemble of coordinate variables consisting of a variable number N of members, said coordinate variables homophysically implementing said qubits, a tuple or vector of variable values assigned to said first ensemble of coordinate variables representing a many-variable (MV) configuration point, a set of such MV configuration points constituting an MV configuration space, said Hamiltonian data comprising a description of a third plurality K of few-variable (FV) Hamiltonians, each of said FV Hamiltonians involving a corresponding second ensemble of coordinate variables selected from said first ensemble of coordinate variables, said corresponding second ensemble of coordinate variables consisting of a fourth plurality L of members, each of said FV Hamiltonians corresponding to one of said quantum gates, said FV Hamiltonians combining into an MV Hamiltonian, wherein said variable number N is substantially upper-bounded by a first predetermined polynomial of (N b +N g ), said third plurality K is substantially upper-bounded by a second predetermined polynomial of (N b +N g ), said fourth plurality L is substantially upper-bounded by a predetermined logarithm of a third predetermined polynomial of (N b +N g ); 
 providing a third processing means for producing Gibbs data comprising a description of an MV Gibbs operator and a fifth plurality of FV Gibbs operators, said MV Gibbs operator being generated by said MV Hamiltonian, each of said FV Gibbs operators being generated by a corresponding one of said FV Hamiltonians, said MV Gibbs operator inducing an MV signed density, each of said FV Gibbs operators inducing a corresponding one of FV signed densities, wherein said fifth plurality is upper-bounded by a fourth predetermined polynomial of (N b +N g ), both said MV signed density and each of said FV signed densities are associated with a subset of said MV configuration space; 
 whereby said MV signed density encodes said quantum result in the sense that a signed expectation value of a prescribed observable due to said MV signed density is substantially equal to said quantum result, said prescribed observable is selected from the group consisting of the number 1, a predetermined constant, and a prescribed function associated with a subset of said MV configuration space; 
   providing a second means for simulating said MV signed density, said second means comprising:
 providing a first simulating means for determining FV nodal surfaces corresponding to each of said FV signed densities, each of said FV nodal surfaces enclosing a corresponding FV nodal cell in which the corresponding FV signed density is non-negative-valued, said corresponding FV nodal cell being a corresponding subset of said MV configuration space, each pair of MV configuration points in said corresponding subset differing from each other at most in variable values assigned to coordinate variables selected from the corresponding second ensemble of coordinate variables; 
 providing a second simulating means for producing a sixth plurality of samples of FV restricted densities, each of said FV restricted densities being substantially equal to a corresponding one of said FV signed densities restricted to one of the corresponding nodal cells, wherein said sixth plurality is substantially upper-bounded by a fifth predetermined polynomial of (N b +N g ), said samples of said FV restricted densities are non-negative-valued; 
 providing a third simulating means for producing a seventh plurality of samples of an MV restricted density by combining said sixth plurality of samples of FV restricted densities, wherein said seventh plurality is substantially upper-bounded by a sixth predetermined polynomial of (N b +N g ), said samples of said MV restricted density are non-negative-valued; 
 whereby said MV restricted density is substantially equivalent to said MV signed density in the sense that the signed expectation value of said prescribed observable due to said MV restricted density is substantially equal to the signed expectation value of said prescribed observable due to said MV signed density; 
   whereby the solution to said computational problem is obtained by said simulating said MV signed density.   
     
     
         16 . The method of  claim 15 , further comprising a fifth means for computing the signed expectation value of said prescribed observable due to said MV restricted density. 
     
     
         17 . The method of  claim 15 , wherein said MV signed density is associated with an MV symmetry group, said MV symmetry group induces an MV group action on said MV configuration space thereby permutes a first set of MV nodal cells corresponding to said MV signed density, each of said MV nodal cells tiles up said MV configuration space under said MV group action, each of said FV signed densities is associated with a corresponding FV symmetry group, said corresponding FV symmetry group has an order (namely, cardinality) that is substantially upper-bounded by a seventh predetermined polynomial of said variable number N, said corresponding FV symmetry group induces a corresponding FV group action on said MV configuration space thereby permutes a second set of FV nodal cells corresponding to the corresponding FV signed density, a collection of the corresponding FV symmetry groups associated with the FV signed densities generates said MV symmetry group. 
     
     
         18 . The method of  claim 15 , wherein said MV signed density is selected from the group consisting of ground state wavefunctions, Gibbs wavefunctions, Gibbs kernels, Gibbs transition amplitudes, and Wiener densities, said MV signed density is associated with a quantum system, said MV transition operator is a Gibbs operator generated by a total Hamiltonian governing said quantum system, said total Hamiltonian is selected from the group consisting of strongly frustration-free Hamiltonians, ground sate frustration-free Hamiltonians, directly frustration-free Hamiltonians, separately frustration-free Hamiltonians, and sum-of-CFFs Hamiltonians. 
     
     
         19 . The method of  claim 18 , wherein said quantum system is a many-species fermionic system comprising an eighth plurality of fermion species, each of said eighth plurality of fermion species consists of a ninth plurality of identical fermions, said eighth plurality is substantially greater than aN α  for a predetermined pair of positive real numbers a and a, said ninth plurality is substantially less than a predetermined logarithm of bN β  for another predetermined pair of positive real numbers b and β, where N is said variable number. 
     
     
         20 . The method of  claim 18 , wherein said total Hamiltonian is substantially a Feynman-Kitaev Hamiltonian governing substantially a Feynman-Kitaev construct, said Feynman-Kitaev construct provides a means for spectral gap amplification such that the ground state and the excited states of said Feynman-Kitaev Hamiltonian is separated by an amplified spectral gap, said amplified spectral gap is substantially greater than cK −γ  for a predetermined pair of positive real numbers c and γ, where K is said third plurality, said positive real number γ is less than 2.