# US 11,113,623 B2 · Multi-sample system for emulating a quantum computer and methods for use therewith > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,113,623 B2 - Document ID: US11113623B2 - Status: Granted - Kind: B2 - Application number: 17/147,161 - Filed: 2021-01-12 - Published: 2021-05-06 - Granted: 2021-09-07 - Earliest claimed: 2019-06-21 - Assignees: BEIT Inc. - Applicants: Beit Inc. - Inventors: Marcin Briański; Witold Jarnicki; Łukasz Czerwiński - Web page: https://patentgrep.com/patent/US11113623B2 ## CPC - G06F 9/455: Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines - G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms - 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 - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A system is presented for emulating sampling of a quantum computer having a plurality of qubits arranged in a grid topology with N columns. The system includes a classical processor that is configured by operational instructions to perform operations that include producing final weights and variable assignments for the N columns based on N iterative passes through the grid topology, wherein each of the N iterative passes generates preliminary weights and variable assignments for a corresponding subset of the N columns, wherein the preliminary weights and variable assignments for a selected column of the corresponding subset based on the preliminary weights and variable assignments generated for a column adjacent to the selected column of the corresponding subset, and wherein the sampling of the quantum computer having the plurality of qubits is emulated by producing a plurality of samples from the N iterative passes based on the final weights and variable assignments for each of the N columns. ## Claims ### Claim 1 A system for emulating sampling of a quantum computer having a plurality of qubits arranged in a grid topology with N columns, the system comprising: a memory that stores operational instructions; at least one classical processor that is configured by the operational instructions to perform operations, the operations including: producing final weights and variable assignments for the N columns based on N iterative passes through the grid topology, wherein each of the N iterative passes generates preliminary weights and variable assignments for a number of columns of the N columns based on preliminary weights and variable assignments generated for an adjacent column for each of the number of columns, wherein final weights and variable assignments are generated for a final column of the N columns for each of the N iterative passes based on the preliminary weights and variable assignments generated for a column of the N columns adjacent to the final column of the N columns, wherein the final weights and variable assignments for the final column of the N columns are used in a next successive pass of the N iterative passes to reduce the number of columns of the N columns where the preliminary weights and variable assignments are regenerated until the N iterative passes are complete and final weights and variable assignments for each of the N columns have been generated; wherein the sampling of the quantum computer having the plurality of qubits is emulated by producing a plurality of samples from the N iterative passes based on the final weights and variable assignments for each of the N columns. ### Claim 2 (depends on 1) The system of claim 1, wherein the plurality of samples includes k samples and wherein the sampling includes: for each sample sl, choosing a random number al uniformly between zero and the preliminary weight of the assignment of sl in column j+1 of the N columns, wherein j is an integer and l is an integer between 1 and k; wherein the generation of the preliminary weights and variable assignments includes, increasing an assignment s in column j+1 of the N columns by the preliminary weight of an assignment t in a column j of the N columns; and decrement al by the preliminary weight of the assignment t in the column j and when this results in sl going from positive to non-positive, set a final weight of the assignment in the column j of the final weights to t. ### Claim 3 (depends on 1) The system of claim 1, wherein a first iterative pass of the N iterative passes generates the final weights and variable assignments for an Nth column of the N columns, based on the preliminary weights and variable assignments generated for a (N−1)st column of the N columns. ### Claim 4 (depends on 3) The system of claim 3, wherein the number of the N columns associated with the first iterative pass of the N iterative passes includes all columns of the N columns in a range between a second column of the N columns and the (N−1)st column of the N columns. ### Claim 5 (depends on 3) The system of claim 3, wherein the first iterative pass of the N iterative passes generates the preliminary weights and variable assignments for a first column of the N columns, based on null weights corresponding to a null column. ### Claim 6 (depends on 3) The system of claim 3, wherein the last iterative pass of the N iterative passes generates the final weights and variable assignments for a first column of the N columns, based on the final weights and variable assignments for a second column of the N columns. ### Claim 7 (depends on 1) The system of claim 1, wherein a pth iterative pass of the N iterative passes generates the final weights and variable assignments for an (N−p+1)st column of the N columns, based on the preliminary weights and variable assignments generated for a (N−p)th column of the N columns. ### Claim 8 (depends on 7) The system of claim 7, wherein the number of the N columns associated with the pth iterative pass of the N iterative passes includes all columns of the N columns in a range between a second column of the N columns and the (N−p)th column of the N columns. ### Claim 9 (depends on 1) The system of claim 1, wherein the grid topology corresponds to a quadratic unconstrained binary optimization (QUBO) model. ### Claim 10 (depends on 1) The system of claim 1, wherein the plurality of samples each corresponds to a Boltzmann distribution. ### Claim 11 A method for emulating sampling of a quantum computer having a plurality of qubits arranged in a grid topology with N columns, the method comprising: performing a first iterative pass of N iterative passes through the grid topology to produce final weights and variable assignments for an Nth column of the N columns, by generating preliminary weights and variable assignments for N−1 columns of the N columns based on preliminary weights and variable assignments generated for an adjacent column for each of the N−1 columns, wherein the final weights and variable assignments are generated for an Nth column based on the preliminary weights and variable assignments generated for an (N−1)st column of the N columns adjacent to the Nth column; performing N−1 other iterative passes of the N iterative passes through the grid topology by: (a) setting p=2; (b) performing an pth pass through the grid topology, to produce final weights and variable assignments for the (N−p+1)st column of the N columns, by regenerating preliminary weights and variable assignments for N−p columns of the N columns based on preliminary weights and variable assignments regenerated for an adjacent column for each of the N−p columns, wherein final weights and variable assignments are generated for an (N−p+1)st column based on the preliminary weights and variable assignments regenerated for an (N−p)th column of the N columns adjacent to the (N−p+1)st column and the final weights and variable assignments generated for the (N−p+2)nd column; (c) incrementing p; (d) repeating steps (b) and (c) until p=N; and (e) performing a final pass through the grid topology, to produce the final weights and variable assignments for a first column of the N columns, based on the final weights and variable assignments generated for a second column of the N columns; wherein the sampling of the quantum computer having the plurality of qubits is emulated by producing a plurality of samples from the N iterative passes based on the final weights and variable assignments for each of the N columns. ### Claim 12 (depends on 11) The method of claim 11, wherein the plurality of samples includes k samples and wherein the sampling includes: for each sample sl, choosing a random number al uniformly between zero and the preliminary weight of the assignment of sl in column j+1 of the N columns, wherein j is an integer and l is an integer between 1 and k; wherein the generation of the preliminary weights and variable assignments includes, increasing an assignment s in column j+1 of the N columns by the preliminary weight of an assignment t in a column j of the N columns; and decrement al by the preliminary weight of the assignment t in the column j and when this results in sl going from positive to non-positive, set a final weight of the assignment in the column j of the final weights to t. ### Claim 13 (depends on 11) The method of claim 11, wherein a first iterative pass of the N iterative passes generates the final weights and variable assignments for an Nth column of the N columns, based on the preliminary weights and variable assignments generated for a (N−1)st column of the N columns. ### Claim 14 (depends on 13) The method of claim 13, wherein the number of the N columns associated with the first iterative pass of the N iterative passes includes all columns of the N columns in a range between a second column of the N columns and the (N−1)st column of the N columns. ### Claim 15 (depends on 13) The method of claim 13, wherein the first iterative pass of the N iterative passes generates the preliminary weights and variable assignments for a first column of the N columns, based on null weights corresponding to a null column. ### Claim 16 (depends on 13) The method of claim 13, wherein the last iterative pass of the N iterative passes generates the final weights and variable assignments for a first column of the N columns, based on the final weights and variable assignments for a second column of the N columns. ### Claim 17 (depends on 11) The method of claim 11, wherein a pth iterative pass of the N iterative passes generates the final weights and variable assignments for an (N−p+1)st column of the N columns, based on the preliminary weights and variable assignments generated for a (N−p)th column of the N columns. ### Claim 18 (depends on 17) The method of claim 17, wherein the number of the N columns associated with the pth iterative pass of the N iterative passes includes all columns of the N columns in a range between a second column of the N columns and the (N−p)th column of the N columns. ### Claim 19 (depends on 11) The method of claim 11, wherein the grid topology corresponds to a quadratic unconstrained binary optimization (QUBO) model. ### Claim 20 A system for emulating sampling of a quantum computer having a plurality of qubits arranged in a grid topology with N columns, the system comprising: a memory that stores operational instructions; at least one classical processor that is configured by the operational instructions to perform operations, the operations including: performing a first pass through the grid topology, wherein the first pass includes iteratively generating preliminary weights and variable assignments for N−1 columns of the N columns based on preliminary weights generated for a preceding adjacent column for each of the N−1 columns in a first order from a first column in the N columns to a (N−1)st column of the N columns, wherein final weights are generated for the Nth column based on the preliminary weights generated for a (N−1)st column of the N columns; and performing a second pass through the grid topology by producing final weights and variable assignments for the remaining N−1 columns of the N columns, wherein the second pass includes iteratively generating final weights and variable assignments for N−1 columns of the N columns based on final weights generated for a preceding adjacent column for each of the N−1 columns in a second order from the (N−1)st column of the N columns to the first column of the N columns; wherein the sampling of the quantum computer having the plurality of qubits is emulated by a sample based on the final weights and variable assignments for each of the N columns.