# US 2022/0067245 A1 · Low-cost linear orders for quantum-program simulation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0067245 A1
- Document ID: US20220067245A1
- Status: Published application
- Kind: A1
- Application number: 17/070,861
- Filed: 2020-10-14
- Published: 2022-03-03
- Earliest claimed: 2020-08-12
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Damian Silvio STEIGER; Thomas HAENER; Martin Henri ROETTELER; Helmut Gottfried KATZGRABER
- Web page: https://patentgrep.com/patent/US20220067245A1

## CPC

- G06F 30/27: using machine learning, e.g. artificial intelligence, neural networks, support vector machines [SVM] or training a model
- G06F 30/3308: using simulation
- G06N 3/126: Evolutionary algorithms, e.g. genetic algorithms or genetic programming
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 10/00: Quantum computing, i.e. information processing based on quantum-mechanical phenomena
- G06N 10/20: Models of quantum computing, e.g. quantum circuits or universal quantum computers
- G06F 8/4434: {Reducing the memory space required by the program code}
- 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

In a method to digitally simulate an evolving quantum state of a qubit register of a quantum computer, the quantum state is represented as a state vector of complex-valued amplitudes, where each amplitude is associated with an individual qubit of the qubit register. A directed acyclic graph defining a set of quantum gates of a quantum-computer program is then received. A linear order for the DAG is constructed by minimizing a partial cost function successively re-computed during construction of the linear order, the partial cost function approximating a cost of transforming the state vector according to a subset of the set of quantum gates applied in the linear order. The state vector is transformed according to the set of quantum gates applied in the linear order, and one or more of the complex-valued amplitudes of the transformed state vector are computationally output.

## Claims

### Claim 1

Enacted in a computer system, a method to digitally simulate an evolving quantum state of a qubit register of a quantum computer, the method comprising:
representing the quantum state as a state vector of complex-valued amplitudes, where each amplitude is associated with an individual qubit of the qubit register;
receiving a directed acyclic graph (DAG) defining a set of quantum gates of a quantum-computer program;
constructing a linear order for the DAG by minimizing a partial cost function successively re-computed during construction of the linear order, wherein the partial cost function approximates a cost of transforming the state vector according to a subset of the set of quantum gates applied in the linear order;
transforming the state vector according to the set of quantum gates applied in the linear order; and
computationally outputting one or more of the complex-valued amplitudes of the transformed state vector in a form receivable as input to a computer program.

### Claim 2 (depends on 1)

The method of claim 1 wherein the partial cost function is one of a plurality of partial cost functions successively re-computed during the construction of the linear order, and wherein each of the plurality of partial cost functions approximates a cost of transforming the state vector according to a differently sized subset of the set of quantum gates applied in the linear order.

### Claim 3 (depends on 1)

The method of claim 1 wherein the cost of transforming the state vector comprises a run time or energy expenditure for transforming the state vector on the computer system.

### Claim 4 (depends on 1)

The method of claim 1 wherein the cost function varies depending on a memory layout that defines a bit position of each qubit in the state vector.

### Claim 5 (depends on 1)

The method of claim 1 wherein the cost function varies depending on how many qubits are transformed by a fused gate in the linear order.

### Claim 6 (depends on 1)

The method of claim 1 wherein a cost of transforming the state vector according to the set of quantum gates in the linear order L is given by an overall cost function {tilde over (f)}cost(L), and wherein {tilde over (f)}cost(L)<{tilde over (f)}cost(L′) if the partial cost function {tilde over (f)}partial(L)<{tilde over (f)}partial(L′) for a different linear order L′.

### Claim 7 (depends on 1)

The method of claim 1 wherein the partial cost function approximates a cost of transforming the state vector by application of a single quantum gate.

### Claim 8 (depends on 1)

The method of claim 1 wherein constructing the linear order includes scheduling and clustering the set of quantum gates to reduce the partial cost function.

### Claim 9 (depends on 1)

The method of claim 1 wherein constructing the linear order includes inserting one or more of a memory-layout change node and a gate-fusion node into the DAG.

### Claim 10 (depends on 1)

The method of claim 1 wherein minimizing the partial cost function includes minimizing via one or more of a diffusion Monte Carlo algorithm, a substochastic Monte Carlo algorithm, or an evolutionary algorithm.

### Claim 11

Enacted in a computer system, a method to digitally simulate an evolving quantum state of a qubit register of a quantum computer, the method comprising:
representing the quantum state as a state vector of complex-valued amplitudes, where each amplitude is associated with an individual qubit of the qubit register;
evaluating and storing a plurality of component cost estimates for transforming the state vector in a look-up table in the computer system;
receiving a directed acyclic graph (DAG) defining a set of quantum gates of a quantum-computer program;
constructing a linear order for the DAG by minimizing a partial cost function successively re-computed during construction of the linear order based on the plurality of component cost estimates, wherein the partial cost function approximates a cost of transforming the state vector according to a subset of the set of quantum gates applied in the linear order;
transforming the state vector according to the set of quantum gates applied in the linear order; and
computationally outputting one or more of the complex-valued amplitudes of the transformed state vector in a form receivable as input to a computer program.

### Claim 12 (depends on 11)

The method of claim 11 wherein the plurality of component cost estimates include a cost texec(gi) of applying a quantum gate g at bit position i of the state vector, and wherein texec(gi) is estimated by dividing allowed bit positions bi ∈ {0, 1, . . . , nqubits−1} into different bands b0, b1, . . . , where each band of bit positions bi contains a subset of the allowed bit locations bi, and where nqubits is the number of qubits represented in the state vector.

### Claim 13 (depends on 11)

The method of claim 11 wherein evaluating the plurality of component cost estimates includes recording a benchmark time to transform the state vector on the computer system by application of one or more quantum gates.

### Claim 14 (depends on 13)

The method of claim 13 further comprising assessing performance of the computer system based on the benchmark time.

### Claim 15

Enacted in a computer system, a method to digitally simulate an evolving quantum state of a qubit register of a quantum computer, the method comprising:
representing the quantum state as a state vector of complex-valued amplitudes, where each amplitude is associated with an individual qubit of the qubit register;
receiving a directed acyclic graph (DAG) defining a set of quantum gates of a quantum-computer program;
instantiating a plurality of walkers configured to walk a parameter space of a plurality of candidate linear orders for the DAG;
constructing a linear order for the DAG by minimizing a partial cost function successively re-computed by the plurality of walkers during construction of the linear order, wherein the partial cost function approximates a cost of transforming the state vector according to a subset of the set of quantum gates applied in the linear order;
transforming the state vector according to the set of quantum gates applied in the linear order; and
computationally outputting one or more of the complex-valued amplitudes of the transformed state vector in a form receivable as input to a computer program.

### Claim 16 (depends on 15)

The method of claim 15 wherein each of the plurality of walkers is configured to pre-select a plurality of candidate quantum gates for next execution in the linear order and, by evaluating the partial cost function, identify a selected quantum gate from among the pre-selected plurality of candidate quantum gates.

### Claim 17 (depends on 16)

The method of claim 16 wherein each of the plurality of walkers is configured to compute a memory-layout update and, pursuant to evaluating the partial cost function for the memory-layout update and for application of the selected quantum gate, determine whether to execute the memory-layout update or insert the selected gate in the linear order.

### Claim 18 (depends on 17)

The method of claim 17 wherein computing the memory-layout update includes selecting an updated memory layout from a distribution computed based on memory layouts of other walkers or on a yet unscheduled portion of the DAG.

### Claim 19 (depends on 18)

The method of claim 18 wherein computing the memory-layout update includes providing a low bit position for a quantum gate to be applied in the yet unscheduled portion of the DAG.

### Claim 20 (depends on 15)

The method of claim 15 wherein minimizing the cost function includes adding or removing one or more walkers based on the partial cost function.
