# US 2020/0394545 A1 · Methods for obtaining solutions to multiproduct formulas

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

- Number: US 2020/0394545 A1
- Document ID: US20200394545A1
- Status: Published application
- Kind: A1
- Application number: 16/442,048
- Filed: 2019-06-14
- Published: 2020-12-17
- Earliest claimed: 2019-06-14
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Vadym KLIUCHNIKOV; Guang Hao LOW; Nathan WIEBE
- Web page: https://patentgrep.com/patent/US20200394545A1

## CPC

- G06N 10/60: Quantum algorithms, e.g. based on quantum optimisation, quantum Fourier or Hadamard transforms
- G06F 17/12: Simultaneous equations {, e.g. systems of linear equations}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06N 10/20: Models of quantum computing, e.g. quantum circuits or universal quantum computers
- G16C 10/00: Computational theoretical chemistry, i.e. ICT specially adapted for theoretical aspects of quantum chemistry, molecular mechanics, molecular dynamics or the like
- G16C 20/30: Prediction of properties of chemical compounds, compositions or mixtures
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G16C: COMPUTATIONAL CHEMISTRY; CHEMOINFORMATICS; COMPUTATIONAL MATERIALS SCIENCE

## Abstract

Examples are disclosed relating to obtaining a solution to a multiproduct formula of order m to solve a quantum computing problem comprising a product formula. One example provides a method comprising selecting a set of exponents kj, wherein each kj is a real number and is an exponent in a linear combination of product formulas. Based on the set of exponents kj, a set of pre-factors aj is determined based on an underdetermined solution to an m×M system of linear equations, where M is a number of lower-order product formulas in the linear combination of product formulas. The set of exponents kj and the set of pre-factors aj are used to solve the quantum computing problem comprising the product formula. By minimizing the set of exponents kj and the set of pre-factors aj, sparse solutions to the multiproduct formula are generated, reducing computational time and scaling.

## Claims

### Claim 1

Enacted via execution of stored instructions on a computing device, a method for obtaining a solution to a multiproduct formula of order m to solve a quantum computing problem comprising a product formula, the method comprising:
selecting a set of exponents kj, wherein each kj is a real number and is an exponent in a linear combination of product formulas;
based on the set of exponents kj, determining the set of pre-factors aj based on an underdetermined solution to an m×M system of linear equations in which the exponents are expressed as a Vandermonde matrix Vm,M(k−α)∈m×M, where α is an order of the product formula, and where M is a number of lower-order product formulas in the linear combination of product formulas; and
using the set of exponents kj and the set of pre-factors aj to solve the quantum computing problem comprising the product formula.

### Claim 2 (depends on 1)

The method of claim 1, wherein the m×M system of linear equations is expressed as:
[
V
m
,
M

(
k
-
α
)
]

[
a
1
a
2
⋮
a
M
]

a
→
=
[
1
0
⋮
0
]

e
^
1
,
wherein the quantum computing problem is a Hamiltonian simulation, and wherein the linear combination of product formulas is as follows:
U
k
→

(
Δ
)
=
∑
j
=
1
M

a
j

U
2
k
j

(
Δ
k
j
)
=
e
-
i

H

Δ
+


(
(
N


h


Δ
)
2

m
+
2
)
,
wherein U represents the product formula, Δ is a step size, aj is a set of pre-factors, H is a sum of Hamiltonians h, is a cost function, and N is a number of terms.

### Claim 3 (depends on 2)

The method of claim 2, wherein the linear combination of product formulas is an expression of the symmetric Trotter-Suzuki formula as follows:
U2(Δ)={right arrow over (U)}1(Δ/2)·(Δ/2)=e−iHΔ+(Δ4).

### Claim 4 (depends on 2)

The method of claim 2, wherein α=2, and wherein the Vandermonde matrix is as follows:
[
1
1
…
1
k
1
-
2
k
2
-
2
…
k
M
-
2
⋮
⋮
⋱
⋮
k
1
-
2

m
+
2
k
2
-
2

m
+
2
…
k
M
-
2

m
+
2
]

V
m
,
M

(
k
→
-
2
)
.

### Claim 5 (depends on 4)

The method of claim 4, wherein M=m, and wherein the underdetermined solution to the m×M system of linear equations has the solution:
a
j
=
∏
q
=
{
1
,
…

,
m
}

\

j

k
[
[
{
]
]

j

[
[
}
]
]
2
k
j
2
-
k
q
2
=
Π
q
≠
j

1
1
-
(
k
q
k
j
)
2
.

### Claim 6 (depends on 1)

The method of claim 1, wherein the underdetermined solution to the m×M system of linear equations is determined based on the following linear program:
min
a
→

⊥

a
→


⊥
1

s
.
t
.

V
m
,
M

(
k
→
-
α
)
·
a
→
=
e
1
^


and


k
j
=
j
.

### Claim 7 (depends on 6)

The method of claim 6, wherein the underdetermined solution to the m×M system of linear equations is based on fractional queries to U2, and wherein the exponents kj are arbitrary real numbers.

### Claim 8 (depends on 6)

The method of claim 6, wherein the underdetermined solution to the m×M system of linear equations is determined based on a fractional multiproduct wherein Vm,m({right arrow over (x)}) is chosen such that
x
j
=

sin
2


(
π

(
2

j
-
1
)
8

m
)
∈
(
0
,
1

/

2
)
.

### Claim 9

A computing device, comprising:
a processor; and
a storage device holding instructions that, in response to a request to obtain a solution to a multiproduct formula of order m to solve a quantum computing problem comprising a product formula, cause the processor to:
select a set of exponents kj, wherein each kj is a real number and is an exponent in the following linear combination of product formulas:
U
k
→

(
Δ
)
=
∑
j
=
1
M

a
j

U
2
k
j

(
Δ
k
j
)
=
e
-
i

H

Δ
+


(
(
N


h


Δ
)
2

m
+
2
)
,
wherein U represents the product formula, M is a number of lower-order product formulas comprised in the linear combination of product formulas, Δ is a step size, aj is a set of pre-factors, H is sum of Hamiltonians h, is a cost function, N is a number of terms;
based on the set of exponents kj, determine the set of pre-factors aj based on an underdetermined solution to the following m×M system of linear equations:
[
1
1
…
1
k
1
-
2
k
2
-
2
…
k
M
-
2
⋮
⋮
⋱
⋮
k
1
-
2

m
+
2
k
2
-
2

m
+
2
…
k
M
-
2

m
+
2
]

V
m
,
M

(
k
→
-
2
)

[
a
1
a
2
⋮
a
M
]

a
→
=
[
1
0
⋮
0
]

e
^
1
;
and
use the set of exponents kj and the set of pre-factors aj to solve the quantum computing problem comprising the product formula.

### Claim 10 (depends on 9)

The computing device of claim 9, wherein the linear combination of product formulas is the symmetric Trotter-Suzuki formula:
U2(Δ)={right arrow over (U)}1(Δ/2)·(Δ/2)=e−iHΔ+O(Δ4)

### Claim 11 (depends on 9)

The computing device of claim 9, wherein M=m, and wherein the underdetermined solution to the m×M system of linear equations has the solution:
a
j
=
∏
q
=
{
1
,
…

,
m
}

\

j

k
[
[
{
]
]

j

[
[
}
]
]
2
k
j
2
-
k
q
2
=
Π
q
≠
j

1
1
-
(
k
q
k
j
)
2
.

### Claim 12 (depends on 11)

The computing device of claim 11, wherein the underdetermined solution to the m×M system of linear equations is determined based on the following linear program:
min
a
→

⊥

a
→


⊥
1

s
.
t
.
V
m
,
M

(
k
→
-
α
)
·
a
→
=


and


k
j
=
j
.

### Claim 13 (depends on 11)

The computing device of claim 11, wherein the underdetermined solution to the m×M system of linear equations is based on fractional queries to U2, and wherein the exponents kj are arbitrary real numbers.

### Claim 14 (depends on 11)

The computing device of claim 11, wherein the underdetermined solution to the m×M system of linear equations is determined based on a fractional multiproduct wherein Vm,m({right arrow over (x)}) is chosen such that
x
j
=

sin
2


(
π

(
2

j
-
1
)
8

m
)
∈
(
0
,
1

/

2
)
.

### Claim 15 (depends on 9)

The computing device of claim 9, wherein the computing device is a quantum computing device further comprising:
a register including a plurality of qubits;
a modulator configured to implement a quantum-logic operation on the plurality of qubits according to control-parameter values stored at the storage device; and
a demodulator configured to reveal data reflecting a quantum state of the plurality of qubits; and wherein the controller is operatively coupled to the modulator and to the demodulator.

### Claim 16 (depends on 9)

The computing device of claim 9, wherein the computing device is a classical computing device.

### Claim 17

A quantum-computing device implemented method for simulating time-evolution of a Hamiltonian via a multiproduct formula of order m, comprising:
selecting a set of exponents kj, wherein each kj is a real number and is an exponent in the following linear combination of product formulas:
U
k
→

(
Δ
)
=
∑
j
=
1
M

a
j

U
2
k
j

(
Δ
k
j
)
=
e
-
i

H

Δ
+


(
(
N


h


Δ
)
2

m
+
2
)
;
wherein U represents the product formula, M is a number of lower-order product formulas comprised in the linear combination of product formulas, Δ is a step size, aj is a set of pre-factors, H is sum of Hamiltonians h, is a cost function, N is a number of terms;
based on the set of exponents kj, determining the set of pre-factors aj based on an underdetermined solution to the following m×M system of linear equations:
[
1
1
…
1
k
1
-
2
k
2
-
2
…
k
M
-
2
⋮
⋮
⋱
⋮
k
1
-
2

m
+
2
k
2
-
2

m
+
2
…
k
M
-
2

m
+
2
]

V
m
,
M

(
k
→
-
2
)

[
a
1
a
2
⋮
a
M
]

a
→
=
[
1
0
⋮
0
]

e
^
1
,
wherein the underdetermined solution is based on the following linear program:
min
a
→

⊥

a
→


⊥
1

s
.
t
.
V
m
,
M

(
k
→
-
α
)
·
a
→
=


and


k
j
=
j
;
and
using the set of exponents kj and the set of pre-factors aj to simulating time-evolution of the Hamiltonian.

### Claim 18 (depends on 17)

The quantum-computing device implemented method of claim 17, wherein M=m, and wherein the underdetermined solution to the m×M system of linear equations has the solution:
a
j
=
∏
q
=
{
1
,
…

,
m
}

\

j

k
[
[
{
]
]

j

[
[
}
]
]
2
k
j
2
-
k
q
2
=
Π
q
≠
j

1
1
-
(
k
q
k
j
)
2
.

### Claim 19 (depends on 18)

The quantum-computing device implemented method of claim 18, wherein the underdetermined solution to the m×M system of linear equations is based on fractional queries to U2, and wherein the exponents kj are arbitrary real numbers.

### Claim 20 (depends on 17)

The quantum-computing device implemented method of claim 17, wherein the linear combination of product formulas is the symmetric Trotter-Suzuki formula:
U2(Δ)={right arrow over (U)}1(Δ/2)·(Δ/2)=e−iHΔ+O(Δ4).
