Solving multivariate quadratic problems using digital or quantum annealing

Patent metadata

Field	Value
Publication number	US-2020233643-A1
Application number	US-201916252538-A
Country	US
Kind code	A1
Filing date	Jan 18, 2019
Priority date	Jan 18, 2019
Publication date	Jul 23, 2020
Grant date	—

Abstract

A method may include obtaining a set of multivariate quadratic polynomials associated with a multivariate quadratic problem and generating an Ising Model connection weight matrix “W and an Ising Model bias vector “b” based on the multivariate quadratic polynomials. The method may also include providing the matrix “W” and the vector “b” to an annealing system configured to solve problems written according to the Ising Model and obtaining an output from the annealing system that represents a set of integers. The method may also include using the set of integers as a solution to the multivariate quadratic problem.

First claim

1 . A method comprising:
obtaining a set of multivariate quadratic polynomials associated with a multivariate quadratic problem; generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b”, at least some elements of the matrix “W” determined based on a set of multivariate quadratic polynomials; providing the matrix “W” and the vector “b” to an annealing system configured to solve problems written according to the Ising Model; obtaining an output from the annealing system that represents a set of integers; and using the set of integers as a solution to the multivariate quadratic problem defined by the set of multivariate quadratic polynomials.

2 . The method of claim 1 , wherein the annealing system includes an energy value calculation circuit configured to calculate an energy value used to generate the output, wherein the energy value is based on a value of one or more of the elements in the matrix “W”.

3 . The method of claim 1 , generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” comprises:
linearizing each polynomial in the set of multivariate quadratic polynomials.

4 . The method of claim 3 , generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” further comprises:
adjusting the linearized polynomials for rounding by removing sufficient multiples of the linearized polynomials.

5 . The method of claim 4 , generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” further comprises:
computing an energy function for the adjusted linearized polynomials.

6 . The method of claim 1 , wherein the set of multivariate quadratic polynomials is based on a multivariate cryptography scheme and further comprising using the solution to the multivariate quadratic problem to perform a challenge to the multivariate cryptography scheme.

7 . One or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed, cause a system to perform operations comprising:
obtaining a set of multivariate quadratic polynomials associated with a multivariate quadratic problem; generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b”, at least some elements of the matrix “W” determined based on a set of multivariate quadratic polynomials; providing the matrix “W” and the vector “b” to an annealing system configured to solve problems written according to the Ising Model; obtaining an output from the annealing system that represents a set of integers; and using the set of integers as a solution to the multivariate quadratic problem defined by the set of multivariate quadratic polynomials.

8 . The one or more non-transitory computer-readable storage media of claim 7 , wherein the set of multivariate quadratic polynomials are obtained from a cryptographic technique.

9 . The one or more non-transitory computer-readable storage media of claim 8 , wherein the operations further comprise using the solution to the multivariate quadratic problem to perform a challenge to the multivariate cryptography technique.

10 . The one or more non-transitory computer-readable storage media of claim 7 , wherein the annealing system includes an energy value calculation circuit configured to calculate an energy value used to generate the output, wherein the energy value is based on a value of one or more of the elements in the matrix “W”.

11 . The one or more non-transitory computer-readable storage media of claim 8 , wherein generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” comprises:
linearizing each polynomial in the set of multivariate quadratic polynomials.

12 . The one or more non-transitory computer-readable storage media of claim 11 , wherein generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” further comprises:
adjusting the linearized polynomials for rounding by removing sufficient multiples of the linearized polynomials.

13 . The one or more non-transitory computer-readable storage media of claim 12 , generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” further comprises:
computing an energy function for the adjusted linearized polynomials.

14 . A system comprising:
one or more computer-readable storage media configured to store instructions; and one or more processors communicatively coupled to the one or more computer-readable storage media and configured to, in response to execution of the instructions, cause the system to perform operations, the operations comprising:
obtaining a set of multivariate quadratic polynomials associated with a multivariate quadratic problem;
generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b”, at least some elements of the matrix “W” determined based on a set of multivariate quadratic polynomials;
providing the matrix “W” and the vector “b” to an annealing system configured to solve problems written according to the Ising Model;
obtaining an output from the annealing system that represents a set of integers; and
using the set of integers as a solution to the multivariate quadratic problem defined by the set of multivariate quadratic polynomials.

15 . The system of claim 14 , wherein the set of multivariate quadratic polynomials are obtained from a cryptographic technique, and wherein the operations further comprise using the solution to the multivariate quadratic problem to perform a challenge to the multivariate cryptography technique.

17 . The system of claim 14 , wherein the annealing system includes an energy value calculation circuit configured to calculate an energy value used to generate the output, wherein the energy value is based on a value of one or more of the elements in the matrix “W”.

18 . The system of claim 14 , wherein generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” comprises:
linearizing each polynomial in the set of multivariate quadratic polynomials.

19 . The system of claim 14 , wherein generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” further comprises:
adjusting the linearized polynomials for rounding by removing sufficient multiples of the linearized polynomials.

20 . The system of claim 14 , wherein generating an Ising Model connection weight matrix “W” and an Ising Model bias vector “b” further comprises:
computing an energy function for the adjusted linearized polynomials.

Assignees

• Fujitsu Ltd

Inventors

• MONTGOMERY Hart
• Roy Arnab
• Ohori Ryuichi
• Shimizu Toshiya
• Shimoyama Takeshi
• Yamaguchi Jumpei

Classifications

• H04L9/302 Primary

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F17/12 Primary

  Simultaneous equations {, e.g. systems of linear equations} · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06N20/00

  Machine learning · CPC title