US 2019/0197426 A1Published application

Transformation apparatus, decision apparatus, quantum computation apparatus, and quantum machine learning system

AssigneeNippon Telegraph and Telephone Corporation

InventorsYasuhito KAWANO, Hiroshi SEKIGAWA

Life of this patent

Estimating the term…

Abstract

First, a dual basis B− of B of modulo N is obtained by classical computation. Next, quantum computation is performed using the periodicity of a point sequence included in a sum set of sets obtained by parallel translation of a lattice L(B) by integral multiples of t for a plurality of integers, and an n-dimensional rj=(rj1, . . . , rjn) and rj0 are obtained for j=1 , . . . , m. Subsequently, by classical computation, the closest vector rj(c)=(rj1(c), . . . , rjn(c))∈L(B−) of the n-dimensional vector rj, and the difference vector rj(d)=rj−rj(c)=(rj1(d), . . . , rjn(d)) corresponding to rj(c) are obtained.

Claims16

Dependent claims

A transformation apparatus receiving inputs of a basis B and a target vector t, and, outputting {rj1(c), rj1(d), rj0} and m, M and N that satisfy

(
(
r
11
(
c
)
…
r
1

n
(
c
)
r
21
(
c
)
…
r
2

n
(
c
)
r
31
(
c
)
…
r
3

n
(
c
)
⋮
⋱
⋮
r
m


1
(
c
)
…
r
mn
(
c
)
)
+
(
r
11
(
d
)
…
r
1

n
(
d
)
r
21
(
d
)
…
r
2

n
(
d
)
r
31
(
d
)
…
r
3

n
(
d
)
⋮
⋱
⋮
r
m


1
(
d
)
…
r
mn
(
d
)
)
)

(
t
1
(
d
)
⋮
t
n
(
d
)
)
+
(
e
1
e
2
e
3
⋮
e
m
)

mod


N
=
(
round

(
r
10

N
M
)
round

(
r
20

N
M
)
round

(
r
30

N
M
)
⋮
round

(
r
m


0

N
M
)
)
comprising processing circuitry configured to implement a first classical computer, a quantum state generator, a first quantum Fourier transformation unit, a manipulator, a first observer, a second quantum Fourier transformation unit, a second observer, an inverse quantum Fourier transformation unit, a third observer, and a second classical computer,
wherein n, m, M and N are positive integers;
M<N;
i=1, . . . , n;
j=1, . . . , m;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
round(μ) is an integer closest to μ;
floor(μ) is a maximum integer equal to or less than μ;
ceil(μ) is a minimum integer equal to or more than μ;
det(η) is a determinant of η;
B={b1, . . . , bn} is a basis made up of linearly independent n n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
β is a basis matrix that has n rows and n columns and includes, as elements, the n-dimensional vectors b1, . . . , bn of the basis B;
t=(t1, . . . , tn)T is a target vector having n integer elements ti;
xi is an integer;
L(B) is a lattice {Σi=1, . . . n xibi|xi∈Z, bi∈B};
τ is an n-dimensional vector;
τ+L(B)=L(B)+τ={τ+χ|χ⊂L(B)};
rji(c), rji(d), rj0 and ej are integers;
t(d) is a difference vector t(d)=t−t(c)=(t1(d), . . . , tn(d))T between the target vector t and a closest vector t(c)∈L(B) of the target vector t;
and s is an n-dimensional vector having integer elements,
the first classical computer is configured to select a multiple N of a least common multiple N′ of denominators of elements of an inverse matrix β−1 of the basis matrix β, and to obtain a dual basis B−={(N/N′)b1′, . . . , (N/N′)bn−′} of modulo N, for a dual basis B−′={b1−′, . . . , bn−′} of the basis B of modulo N′,
the quantum state generator is configured to set a quantum state of a register string that includes an index register having ceil(log2(M+1)) quantum bits, a data register having n×ceil(log2(N+1)) quantum bits, and a work register having n×ceil(log2(det(β)+1)) quantum bits to
1

B
R


∑
x
∈
B
R


0
〉


x
〉


0
〉
where BR is a set of points included in [0,N)n,
the first quantum Fourier transformation unit is configured to execute M-dimensional quantum Fourier transform on the index register, and to transform the quantum state of the register string into
1
M


B
R


∑
w
=
0
M
-
1

∑
x
∈
B
R


w
〉


x
〉


0
〉
the manipulator is configured to execute quantum manipulation of changing a quantum state |w|x|0 to a quantum state |w|x|det(β)(yw,x,1−floor(yw,x,1)), . . . , det(β)(yw,x,n−floor(yw,x,n)), on the register string in the quantum state obtained by the first quantum Fourier transformation unit, where x−wt=yw,x,1b1+ . . . +yw,x,nbn is satisfied,
the first observer is configured to observe the work register that stores the quantum state obtained by the manipulator, and to change the quantum states of the index register and the data register to
1
M

∑
w
=
0
M
-
1

(
1

B
R
⋂
(
L

(
B
)
+
s
+
wt
(
d
)
)


∑
x
∈
B
R
⋂
(
L

(
B
)
+
s
+
wt
(
d
)
)


w
〉


x
〉
)
the second quantum Fourier transformation unit is configured to execute N-dimensional quantum Fourier transform on the data register that stores the quantum state after observation by the first observer,
the second observer is configured to observe the data register that stores the quantum state obtained by the second quantum Fourier transformation unit to obtain an observation result (rj1, . . . , rjn),
the inverse quantum Fourier transformation unit is configured to execute M-dimensional inverse quantum Fourier transform on the index register that stores the quantum state after observation by the second observer,
the third observer is configured to observe the index register that stores the quantum state obtained by the inverse quantum Fourier transformation unit to obtain an observation result rj0, and
the second classical computer is configured to receive, as inputs, the dual basis B− obtained by the first classical computer, and the observation results (rj1, . . . , rjn) and rj0 obtained by performing processes of the quantum state generator, the first quantum Fourier transformation unit, the manipulator, the first observer, the second quantum Fourier transformation unit, the second observer, and the third observer, for j=1, . . . , m, and to obtain a closest vector rj(c)=(rj1(c), . . . , rjn(c))∈L(B−) of an n-dimensional vector rj=(rj1, . . . , rjn), and a difference vector rj(d)=rjrj(c)=(rj1(d), . . . , rjn(d)), for a dual lattice L(B−)={Σi−1, . . . , n xib−i|xi∈Z, b−i∈B−} and the n-dimensional vector rj.

341 more elements

A transformation apparatus receiving inputs of an n-dimensional vector aj and g and an integer N′ that satisfy

(
a
11
…
a
1

m
′
a
21
…
a
2

m
′
a
31
…
a
3

m
′
⋮
⋱
⋮
a
n


1
…
a
n


m
′
)

(
X
1
⋮
X
m
′
)
+
(
d
1
d
2
d
3
⋮
d
n
)

mod


N
′
=
(
g
1
g
2
g
3
⋮
g
n
)
and outputting {rji(c), rji(d), rj0} and m, M and N that satisfy
(
(
r
11
(
c
)
…
r
1

n
(
c
)
r
21
(
c
)
…
r
2

n
(
c
)
r
31
(
c
)
…
r
3

n
(
c
)
⋮
⋱
⋮
r
m


1
(
c
)
…
r
mn
(
c
)
)
+
(
r
11
(
d
)
…
r
1

n
(
d
)
r
21
(
d
)
…
r
2

n
(
d
)
r
31
(
d
)
…
r
3

n
(
d
)
⋮
⋱
⋮
r
m


1
(
d
)
…
r
mn
(
d
)
)
)

(
t
1
(
d
)
⋮
t
n
(
d
)
)
+
(
e
1
e
2
e
3
⋮
e
m
)

mod


N
=
(
round

(
r
10

N
M
)
round

(
r
20

N
M
)
round

(
r
30

N
M
)
⋮
round

(
r
m


0

N
M
)
)
comprising processing circuitry configured to implement a first classical computer, a quantum state generator, a first quantum Fourier transformation unit, a manipulator, a first observer, a second quantum Fourier transformation unit, a second observer, an inverse quantum Fourier transformation unit, a third observer, and a second classical computer,
wherein n, m, m′, M, N and N′ are positive integers;
M<N;
i=1, . . . , n;
j=1, . . . , m;
u=1, . . . , n;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
round(μ) is an integer closest to μ;
floor(μ) is a maximum integer equal to or less than μ;
ceil(μ) is a minimum integer equal to or more than μ;
det(η) is a determinant of η;
B={b1, . . . , bn} is a basis made up of linearly independent n n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
β is a basis matrix that has n rows and n columns and includes, as elements, the n-dimensional vectors b1, . . . , bn of the basis B;
t=(t1, . . . , tn)T is a target vector having n integer elements ti;
xi is an integer;
L(B) is a lattice {Σi=1, . . . n xibi|xi∈Z, bi∈B};
τ is an n-dimensional vector;
τ+L(B)=L(B)+τ={τ+χ|χ∈L(B)};
rji(c), rji(d), rj0, ej, Xj and di are integers;
t(d) is a difference vector t(d)=t−t(c)=(t1(d), . . . , tn(d))T between the target vector t and a closest vector t(c)∈L(B) of the target vector t;
s is an n-dimensional vector having integer elements;
aj is an n-dimensional vector aj=(a1j, . . . , anj)T having n integer elements a1j, . . . , anj;
g is an n-dimensional vector g=(g1, . . . , gn)T having n elements g1, . . . , gn;
and εu is an n-dimensional unit vector εu=(0 , . . . , 1, 0, . . . , 0)T where a u-th element is 1 and other elements are 0,
the first classical computer is configured to set an LLL-reduced basis computed from {a1, . . . , am′, N′ε1, . . . , N′εn} as the basis B, to obtain a dual basis B−={(N/N′)b1−′, . . . , (N/N′)bn−′} of modulo N for a dual basis B−′={b1−′, . . . , bn−′} of modulo N′ of the basis B, and to set t=g,
the quantum state generator is configured to set a quantum state of a register string that includes an index register having ceil(log2(M+1)) quantum bits, a data register having n×ceil(log2(N+1)) quantum bits, and a work register having n×ceil(log2(det(β)+1)) quantum bits to
1

B
R


∑
x
∈
B
R


0
〉


x
〉


0
〉
where BR is a set of points included in [0,N)n,
the first quantum Fourier transformation unit is configured to execute M-dimensional quantum Fourier transform on the index register, and to transform the quantum state of the register string into
1
M


B
R


∑
w
=
0
M
-
1

∑
x
∈
B
R


w
〉


x
〉


0
〉
,
the manipulator is configured to execute quantum manipulation of changing a quantum state |w|x|0 to a quantum state |wx|det(β)(yw,x,1−floor(yw,x,1)), . . . , det(β)(yw,x,n−floor(yw,x,n)), on the register string in the quantum state obtained by the first quantum Fourier transformation unit, where x−wt=yw,x,1b1+ . . . +yw,x,nbn is satisfied,
the first observer is configured to observe the work register that stores the quantum state obtained by the manipulator to change the quantum states of the index register and the data register to
1
M

∑
w
=
0
M
-
1

(
1

B
R
⋂
(
L

(
B
)
+
s
+
wt
(
d
)
)


∑
x
∈
B
R
⋂
(
L

(
B
)
+
s
+
wt
(
d
)
)


w
〉


x
〉
)
,
the second quantum Fourier transformation unit is configured to execute N-dimensional quantum Fourier transform on the data register that stores the quantum state after observation by the first observer,
the second observer is configured to observe the data register that stores the quantum state obtained by the second quantum Fourier transformation unit to obtain an observation result (rj1, . . . , rjn),
the inverse quantum Fourier transformation unit is configured to execute M-dimensional inverse quantum Fourier transform on the index register that stores the quantum state after observation by the second observer,
the third observer is configured to observe the index register that stores the quantum state obtained by the inverse quantum Fourier transformation unit to obtain an observation result rj0, and
the second classical computer is configured to receive, as inputs, the dual basis B− obtained by the first classical computer, and the observation results (rj1, . . . , rjn) and rj0 obtained by performing processes of the quantum state generator, the first quantum Fourier transformation unit, the manipulator, the first observer, the second quantum Fourier transformation unit, the second observer, and the third observer, for j=1, . . . , m, and to obtain a closest vector rj(c)=(rj1(c), . . . , rjn(c))∈L(B−) of an n-dimensional vector rj=(rj1, . . . , rjn), and a difference vector rj(d)=rj−rj(c)=(rj1(d), . . . , rjn(d), for a lattice L(B−)={Σi=1, . . . , n xib−i|xi∈Z, b−i∈B−} and the n-dimensional vector rj.

428 more elements

A decision apparatus outputting information representing whether a difference vector t(d) satisfying

(
(
r
11
(
c
)
⋯
r
1

n
(
c
)
r
21
(
c
)
⋯
r
2

n
(
c
)
r
31
(
c
)
⋯
r
3

n
(
c
)
⋮
⋱
⋮
r
m


1
(
c
)
⋯
r
mn
(
c
)
)
+
(
r
11
(
d
)
⋯
r
1

n
(
d
)
r
21
(
d
)
⋯
r
2

n
(
d
)
r
31
(
d
)
⋯
r
3

n
(
d
)
⋮
⋱
⋮
r
m


1
(
d
)
⋯
r
mn
(
d
)
)
)

(
t
1
(
d
)
⋮
t
n
(
d
)
)
+
(
e
1
e
2
e
3
⋮
e
m
)


mod


N
=
(
round

(
r
10

N
M
)
round

(
r
20

N
M
)
round

(
r
30

N
M
)
⋮
round

(
r
m


0

N
M
)
)
satisfies ∥t(d)∥≤L or satisfies ∥t(d)∥>γL,
the decision apparatus comprising processing circuitry configured to implement a hyperplane distance estimator, and a decision unit,
wherein n, m, N and M are positive integers;
M<N;
i=1, . . . , n;
j=1, . . . , m;
ηT is a transpose of η;
round(μ) is an integer closest to μ;
floor(μ) is a maximum integer equal to or less than μ;
ceil(μ) is a minimum integer equal to or more than μ;
ABS(μ) is an absolute value of μ;
∥η∥ is a length of η;
B={b1, . . . , bn} is a basis made up of linearly independent n
n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
t=(t1, . . . , tn)T is a target vector having n integer elements ti;
xi is an integer;
L(B) is a lattice {Σi=1, . . . , n xibi|xi∈Z, bi∈B};
τ is an n-dimensional vector;
τ+L(B)=L(B)+τ={τ+χ|χ∈L(B)};
B− is a dual basis of modulo N and is an LLL-reduced basis of {τ|<τ, χ>=0 mod N for all χ⊂L(B)};
<τ, χ> is an inner product of τ and χ;
L(B−) is a dual lattice L(B−)={Σi=1, . . . , n xib−i|xi∈Z, b−i∈B−};
rji(c), rji(d), rj0 and ej are integers;
rj(c) is an n-dimensional vector rj(c)=(rj1(c), . . . , rjn(c))∈L(B−);
rj(d) is an n-dimensional vector rj(d)=(rj1(d), . . . , rjn(d));
t(d) is a difference vector t(d)=t−t(c)=(t1(d), . . . , tn(d))T between the target vector t and a closest vector t(c)∈L(B) of the target vector t;
and L and γ are positive integers,
a certain hyperplane among a finite number of hyperplanes whose normal vector is an n-dimensional vector sj(d) satisfying rj=rj(c)+rj(d)=sj=sj(c)+sj(d) and sj(c)∈L(B−) corresponds to the difference vector t(d),
the hyperplane distance estimator is configured to obtain an evaluation value Evalq based on a distance between a hyperplane and an origin, the hyperplane being closest to the origin among the hyperplanes included in the finite number of hyperplanes, and
the decision unit is configured to output information that ∥t(d)∥≤L is satisfied when Evalq≤L is satisfied, and outputs information that ∥t(d)∥>γL is satisfied when Evalq>L is satisfied.

222 more elements

A decision apparatus, comprising

processing circuitry configured to implement a first classical computer, a first quantum state generator, a second quantum state generator, a first swap tester, a third quantum state generator, a fourth quantum state generator, a second swap tester, and a second classical computer,
wherein n and N are positive integers;
i=1, . . . , n;
im is an imaginary unit;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
∥η∥ is a length of η;
<τ, χ> is an inner product of τ and χ;
η1⊆η2 represents that η1 is a subset of η2;
B={b1, . . . , bn} is a basis made up of linearly independent n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
L(B) is a lattice {Σi=1, . . . , n xibi|xi∈Z, bi∈B};
L(B−) is a dual lattice of modulo N and is defined for the basis B and the integer N;
xi is an integer;
B− is a dual basis of B of modulo N;
R⊆Zn is a partial region belonging to an n-dimensional space made up of integer elements;
t1=(t1,1, . . , t1,n)T is a target vector having n integer elements t1,i;
t2=(t2,1, . . . , t2,n)T is a target vector having n integer elements t2,i;
t1(d) is a difference vector t1(d)=t1−t1(c)=(t1,1(d), . . . , t1,n(d)) between the target vector t1 and a closest vector t1(c)∈L(B) of the target vector t1;
and t2(d) is a difference vector t2(d)=t2−t2(c)=(t2,1(d), . . . , t2,n(d)) between the target vector t2 and a closest vector t2(c)∈L(B) of the target vector t2, and
the first classical computer is configured to use the basis B and the integer N and obtain and output the dual basis B−,
the first quantum state generator is configured to generate a plurality of registers in a following quantum state

ϕ
〉
0
=
1

(
R
⋂
L

(
B
_
)
)


∑
x
∈
R
⋂
L

(
B
_
)


x
〉
,
the second quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕ0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t


1
=
1

(
R
⋂
L

(
B
_
)
)


∑
x
∈
R
⋂
L

(
B
_
)

e
2


π


i
m

〈
t


1
,

x
〉
/
N


x
〉
,
the first swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕ0 and the register that stores a quantum state |ϕt1, and decide whether a result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt1 is receipt or denied,
the third quantum state generator is configured to generate a plurality of registers in a following quantum state

ϕ
〉
0
=
1

(
R
⋂
L

(
B
_
)
)


∑
x
∈
R
⋂
L

(
B
_
)


x
〉
,
the fourth quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕ0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t


1
=
1

(
R
⋂
L

(
B
_
)
)


∑
x
∈
R
⋂
L

(
B
_
)

e
2


π


i
m

〈
t


1
,

x
〉
/
N


x
〉
,
the second swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕ0 and the register that stores a quantum state |ϕt2, and decide whether a result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt2 is receipt or denied, and
the second classical computer is configured to use the result of the swap test to compute a probability p1 that the result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt1 is receipt and a probability p2 that the result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt2 is receipt, and output information indicating that ∥t1(d)∥≤∥t2(d)∥ when p1≥p2 and output information indicating that ∥t1(d)∥>∥t2(d)∥ when p1<p2, or output information indicating that ∥t1(d)∥<∥t2(d)∥ when p1>p2 and output information indicating that ∥t1(d)∥≥|t2(d)∥ when p1≤p2.

215 more elements

A computation apparatus, comprising

processing circuitry configured to implement an initial setter, a basis selector, a representative selector, a child node generator, a classical computer, a node selector, a controller, a first quantum state generator, a second quantum state generator, and a swap tester,
wherein n, N, v(D) and D are positive integers;
i=1, . . . , n;
im is an imaginary unit;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
∥η∥ is a length of η;
η1⊆η2 represents that η1 is a subset of η2;
η1∈η2 represents that η1 is a proper subset of η2;
<τ, χ> is an inner product of τ and χ;
B={b1, . . . , bn} is a basis made up of linearly independent n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
L(B) is a lattice {Σi=1, . . . , n xibi|xi∈Z, bi∈B};
L(B−) is a dual lattice L(B−) of modulo N and is defined for the basis B and the integer N;
xi is an integer;
B− is a dual basis of B of modulo N;
R⊆Zn is a partial region belonging to an n-dimensional space made up of integer elements;
and t=(t1, . . . , tn)T is a target vector having n integer elements ti,
the initial setter is configured to receive a pair (B, t) as an input, and set a node (B0, t(0))=(B, t) made up of a pair of a basis B0 and a target vector t(0),
the basis selector is configured to select a basis BD of a sub-lattice L(BD)⊂L(BD−1) of a lattice L(BD−1),
the representative selector is configured to assume (cD,0+L(BD))∪(cD,1+L(BD))∪ . . . ∪(cD,ν(D)−1+L(BD))=L(BD−1),
select representatives cD,0, cD,1, . . . , cD,ν(D)−1 satisfying a condition that (cD,κ1+L(BD))∩(cD,κ2+L(BD)) is empty, when κ1≠κ2 for arbitrary κ1 and κ2 that are equal to or more than 0 and equal to or less than ν(D), where each of the representatives cD,0, cD,1, . . . , cD,ν(D)−1 is an n-dimensional vector having integer elements,
the child node generator is configured to select a node (BD, t(D−1)−cD,k′) for k′=0, 1, . . . , ν(D)−1, as a child node of a node (BD−1, t(D−1)),
the classical computer is configured to use the basis BD and the integer N and obtain and output the dual basis BD−,
the first quantum state generator is configured to generate a plurality of registers in a following quantum state

ϕ
〉
D
,
0
=
1

(
R
⋂
L

(
B
_
D
)
)


∑
x
∈
R
⋂
L

(
B
_
D
)


x
〉
,
the second quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕD,0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t


(
D
,
k
′
)
=
1

(
R
⋂
L

(
B
_
D
)
)


∑
x
∈
R
⋂
L

(
B
_
D
)

e
2


π


i
m

〈
t


(
D
-
1
)
-
C
D
,
k
′
,

x
〉
/
N


x
〉
,
the swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕD,0 and the register that stores a quantum state |ϕt(D,k′) for k′=0, 1, . . . , ν(D)−1, and decide whether a result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt(D,k′) is receipt or denied,
the node selector is configured to use a result of the swap test, compute a probability pD,k′ that the result of the swap test for the pair of the quantum state |ϕD,0 and the quantum state |ϕt(D,k′) is receipt, and select a node (BD, t(D−1)−cD,kmax) corresponding to a highest probability pD,kmax among the probabilities pD,0, . . . , pD,ν(D)−1, where kmax∈{0, 1, . . . , ν(D)−1}, and
the controller is configured to obtain a shortest difference vector t(BD,d) between t(D−1)−CD,kmax and a lattice L(BD), to output the difference vector t(BD, d) as a difference vector t(d) and output a closest vector tBD, c)=t−t(BD, d)∈L(BD) as a closest vector t(c) when a length of the difference vector t(BD, d) is smaller than a reference value, and to execute control of setting D+1 as a new D and further setting t(D)=t(D−1)−cD,kmax and of re-executing processes of the basis selector, the representative selector, the child node generator, the classical computer, the first quantum state generator, the second quantum state generator, the swap tester, the node selector, and the controller when the length of the difference vector t(BD, d) is equal to or more than the reference value.

142 more elements

A computation apparatus receiving n-dimensional vectors aj and g and an integer N as inputs, and outputting (X1, . . . , Xm)T satisfying

(
a
11
⋯
a
1

m
a
21
⋯
a
2

m
a
31
⋯
a
3

m
⋮
⋱
⋮
a
n


1
⋯
a
nm
)

(
X
1
⋮
X
m
′
)

(
d
1
d
2
d
3
⋮
d
n
)


mod


N
=
(
g
1
g
2
g
3
⋮
g
n
)
comprising processing circuitry configured to implement a first classical computer, a first quantum state generator, a second quantum state generator, a swap tester, a selector, and a second classical computer,
wherein n, m and N are positive integers;
i=1, . . . , n;
j=1, . . . , m;
im is an imaginary unit;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
<τ, χ> is an inner product of τ and χ;
η1⊆η2 represents that η1 is a subset of η2;
B={b1, . . , bn} is a basis made up of linearly independent n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
L(B) is a lattice {Σi=1, . . . , n xibi|xi−Z, bi∈(B)};
L(B−)is a dual lattice L(B−) of modulo N and is defined for the basis B and the integer N;
Xi is an integer;
B− is a dual basis of B of modulo N;
R⊆Zn is a partial region belonging to an n-dimensional space made up of integer elements;
aj is an n-dimensional vector aj=(a1j, . . , ajn)T having n integer elements a1j, . . . , anj;
g is an n-dimensional vector g=(g1, . . . , gn)T having n elements g1, . . . , gn;
d is an n-dimensional vector d=(d1, . . . , dn)T having n elements d1, . . . , dn;
and εu is an n-dimensional unit vector εu=(0, . . . , 1, 0, . . . , 0)T where a u-th element is 1 and other elements are 0,
each of X1, . . . , Xm is obtained by a process corresponding to any of depths D=1, . . . , m, Xj obtained by the process corresponding to the depth D is Xj(D)∈{X1, . . . , Xm}, a value of Xj(D) is obtained by the process corresponding to the depth D is aj(D), the n-dimensional vector aj corresponding to Xj obtained by the process corresponding to the depth D is aj(D)∈{a1, . . . , am}, AD−1=(aj(D) aj(D 1) . . . aj(m)), X′D−1=(Xj(D), Xj(D+1), . . . , Xj(m))T, and
g
D
-
1
′
=
g
-
∑
j
′
=
1
D
-
1

α
j

(
j
′
)

a
j

(
j
′
)
the first classical computer is configured to obtain and output a dual basis BD− of modulo N, of an LLL-reduced basis BD of a lattice defined by {aj(D+1)T aj(D+2)T . . . aj(m)T Nε1T . . . NεnT}, in the process corresponding to the depth D,
the first quantum state generator is configured to generate a plurality of registers in a quantum state

ϕ
〉
D
,
0
=
1

(
R
⋂
L

(
B
_
D
)
)


∑
x
∈
R
⋂
L

(
B
_
D
)


x
〉
in the process corresponding to the depth D,
the second quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕD,0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t


(
D
,
j
′
)
=
1

(
R
⋂
L

(
B
_
D
)
)


∑
x
∈
R
⋂
L

(
B
_
D
)

e
2


π


i
m

〈
g
D
-
1
′


T
-
j
′
·
a
j

(
D
)
T
,
x
〉
/
N


x
〉
for j′=0, 1, 2, . . . , N−1, in the process corresponding to the depth D,
the swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕD,0 and the register that stores a quantum state |ϕt(D,j′) for j′=0, 1, 2, . . . , N−1, and decide whether a result of the swap test for the pair of the quantum state |ϕD,0 and the quantum state |ϕt(D,j′) is receipt or denied, in the process corresponding to the depth D,
the selector is configured to use a result of the swap test and compute a probability pD,j′ that a result of the swap test for the pair of the quantum state |ϕD,0 and the quantum state |ϕt(D,j′) is receipt, output, as aj(D), jmax∈{0, 1, 2, . . . , N−1} corresponding to a highest probability pD,jmax among the probabilities pD,0, pD,1, . . . , pD,N−1, and further output gD′=gD−1′−aj(D)•aj(D), in the process corresponding to the depth D, and
the second classical computer is configured to perform control of outputting (X1, . . . , Xm)T obtained by arranging αj(1), . . . , αj(m) when the selector outputs aj(D) for all D=1, . . . , m, and of re-executing processes of the first classical computer, the first quantum state generator, the second quantum state generator, the swap tester, the selector and the second classical computer when the selector does not output aj(D) for any D=1, . . . , m.

249 more elements

A decision apparatus, comprising

processing circuitry configured to implement a first classical computer, a first quantum state generator, a second quantum state generator, a first swap tester, a third quantum state generator, a fourth quantum state generator, a second swap tester, and a second classical computer,
wherein n and n′ are positive integers;
n′>n;
i=1, . . . , n;
i′=1, . . . ,n′;
im is an imaginary unit;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
∥η∥ is a length of η;
<τ, χ> is an inner product of τ and χ;
η1⊆η2 represents that η1 is a subset of η2;
B={b1, . . . , bn} is a basis made up of linearly independent n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
L(B) is a lattice {Σi=1, . . . , n xibi|xi∈Z, bi∈B};
xi is an integer;
β is a basis matrix that has n rows and n columns and includes the n-dimensional vectors b1, . . . , bn of the basis B as elements;
α is a matrix made up of integer elements having n rows;
t1=(t1,1, . . . , t1,n)T is a target vector having n integer elements t1,i;
t2=(t2,1, . . . , t2,n)T is a target vector having n integer elements t2,i;
t1(d) is a difference vector t1(d)=t1−t1(c)=(t1,1(d), . . . , t1,n(d)) between the target vector t1 and a closes vector t1(c)∈L(B) of the target vector t1;
and t2(d) is a difference vector t2(d)=t2−t2(c)=(t2,1(d), . . . , t2,n(d)) between the target vector t2 and a closest vector t2(2)∈L(B) of the target vector t2, and
the first classical computer is configured to select the matrix α where an Hermite normal form of a transposed matrix β′T of a matrix β′=(αβ) obtained by arranging the matrix α and the basis matrix β in a horizontal direction is a matrix having diagonal elements of 1, obtain a unimodular matrix β−′ satisfying β−′β′T=H′ for an Hermite normal form matrix H′, set a basis made up of row vectors b1′, . . . , bn′ of the matrix β′=(b1′, . . . , bn′)T as B′, set a basis made up of row vectors b1−′, . . . , bn−′ of the unimodular matrix β−′=(b1−′, . . . , bn−′)T as B−′, and obtain a target vector t1′=(t′1,1, . . . , t′1,n′)T∈span(B′) having n′ integer elements t′1,i′ belonging to a space span(B′) spanned by the basis B′ and a target vector t2′=(t′2,1, . . . , t′2,n′)T∈(B′) having n′ integer elements t′2,i′,
Proj(t1′)=(0, t1) and Proj(t2′)=(0, t2), Proj(μ) represents a projection onto an n-dimensional vector space where first n′−n elements of μ are 0, L(B−′) is the lattice L(B−′)=
{Σi′=1, . . . , n′ xi′b−′i′|xi′∈Z, b−′i′∈B−′}, xi′ is an integer, and R⊆n′ is a partial region belonging to the n′-dimensional space made up of integer elements,
the first quantum state generator is configured to generate a plurality of registers in a following quantum state

ϕ
〉
0
=
1

(
R
⋂
L

(
B
_
′
)
)


∑
x
∈
R
⋂
L

(
B
_
′
)


x
〉
,
the second quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕ0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t


1
′
=
1

(
R
⋂
L

(
B
_
′
)
)


∑
x
∈
R
⋂
L

(
B
_
′
)

e
2


π


i
m

〈
t


1
′
,

x
〉


x
〉
,
the first swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕ0 and the register that stores a quantum state |ϕt1′, and decide whether a result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt1′ is receipt or denied,
the third quantum state generator is configured to generate a plurality of registers in a following quantum state

ϕ
〉
0
=
1

(
R
⋂
L

(
B
_
′
)
)


∑
x
∈
R
⋂
L

(
B
_
′
)


x
〉
,
the fourth quantum state generator is configured to perform quantum manipulation for one or some of the registers in the quantum state |ϕ0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t


2
′
=
1

(
R
⋂
L

(
B
_
′
)
)


∑
x
∈
R
⋂
L

(
B
_
′
)

e
2


π


i
m

〈
t


2
′
,

x
〉


x
〉
,
the second swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕ0 and the register that stores a quantum state |ϕt2′, and decide whether a result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt2′ is receipt or denied, and
the second classical computer is configured to use the result of the swap test and compute a probability p1 that the result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt1 is receipt and a probability p2 that the result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt2 is receipt, and output information indicating that ∥t1(d)∥≤∥t2(d)∥ when p1≥p2 and output information indicating that ∥t1(d)∥>∥t2(d)∥ when p1<p2, or output information indicating that ∥t1(d)∥<∥t2(d)∥ when p1>p2 and output information indicating that ∥t1(d)∥≥|t2(d)∥ when p1≤p2.

226 more elements

A computation apparatus, comprising

processing circuitry configured to implement an initial setter, a basis selector, a representative selector, a child node generator, a classical computer, a node selector, a controller, a first quantum state generator, a second quantum state generator, and a swap tester,
wherein n, n′, N, ν(D) and D are positive integers, n′>n;
i=1, . . . , n;
i=1, . . . , n′;
im is an imaginary unit;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
∥η∥ is a length of η;
η1⊆η2 represents that η1 is a subset of η2;
<τ, χ> is an inner product of τ and χ;
η1⊂η2 represents that η1 is a proper subset of η2;
B={b1, . . . , bn} is a basis made up of linearly independent n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
L(B) is a lattice {Σi=1, . . . , n xibi|xi∈Z, bi∈B};
xi is an integer;
R⊆Zn′ is a partial region belonging to an n′-dimensional space made up of integer elements;
and t=(t1, . . . , tn)T is a target vector having n integer elements ti,
the initial setter is configured to receive a pair (B, t) as an input, and set a node (B0, t(0))=(B, t) made up of a pair of a basis B0 and a target vector t(0),
the basis selector is configured to select a basis BD of a sub-lattice L(BD)⊂(BD−1) of a lattice L(BD−1), where βD is a basis matrix that has n rows and n columns and includes n-dimensional vectors bD,1, . . . , bD,n of the basis BD={bD,1 , . . . , bD,n} as row vectors, and αD is a matrix made up of integer elements having n rows,
(cD,0+L(BD))∪(cD,1+L(BD))∪ . . . ∪(cD,ν(D)−1+L(BD))=L(BD−1),
the representative selector is configured to select representatives cD,0, cD,1, . . . , cD,ν(D)−1 satisfying a condition that (cD,κ1+L(BD))∩(cD,κ2+L(BD)) is empty when κ1≠κ2 for arbitrary κ1 and κ2 that are equal to or more than 0 and equal to or less than ν(D), where each of the representatives cD,0, cD,1, . . . , cD,ν(D)−1 is an n-dimensional vector having integer elements,
the child node generator is configured to select a node (BD, t(D−1)−cD,k′) for k′=0, 1, . . . , ν(D)−1, as a node (BD−1, t(D−1)),
the classical computer is configured to select the matrix αD where an Hermite normal form of a transposed matrix βD′T of a matrix βD′=(αD βD) obtained by arranging the matrix αD and the basis matrix βD in a horizontal direction is a matrix having diagonal elements of 1, obtain a unimodular matrix βD−′ satisfying βD−′ βD′T=H′ for an Hermite normal form matrix H′, set a basis made up of row vectors bD,1′, . . . , bD,n′′ of the matrix βD′=(bD,1′, . . . , bD,n′′)T as BD′, set a basis made up of row vectors bD,1−′, . . . , bD,n′−′ of the unimodular matrix βD−′=(bD,1−′, . . . , bD,n′−′)T as BD−′, and obtain a target vector t(D)′=(t′D,1, . . . , t′D,n′)T∈span(BD′) having n′ integer elements t′D,i′ belonging to a space span(BD′) spanned by the basis BD′,
Proj(t′D−1,k′)=(0, t(D−1)−cD,k′), Proj(μ) represents a projection onto an n-dimensional vector space where first n′−n elements of μ are 0, L(B−′) is the lattice L(B−′)={Σi′=1, . . . , n′ xi′b−′i′|xi′∈Z, b−′i′∈B−′}, xi′ is an integer, and R⊆Zn′ is a partial region belonging to the n′-dimensional space made up of integer elements,
the first quantum state generator is configured to generate a plurality of registers in a following quantum state

ϕ
〉
D
,
0
=
1

(
R
⋂
L

(
B
_
D
′
)
)


∑
x
∈
R
⋂
L

(
B
_
D
′
)


x
〉
,
the second quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕD,0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t

(
D
,
k
′
)
=
1

(
R
⋂
L

(
B
_
D
′
)
)


∑
x
∈
R
⋂
L

(
B
_
D
′
)

e
2


π


i
m

〈
t
D
-
1
,
k
′
′
,
x
〉


x
〉
,
the swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕD,0 and the register that stores a quantum state |ϕt(D,k′) for k′=0, 1, . . . , ν(D)−1, and decide whether a result of the swap test for the pair of the quantum state |ϕ0 and the quantum state |ϕt(D,k′) is receipt or denied,
the node selector is configured to use a result of the swap test, compute a probability pD,k′ that the result of the swap test for the pair of the quantum state |ϕD,0 and the quantum state |ϕt(D,k′) is receipt, and select a node (BD, t(D−1)−cD,kmax) corresponding to a highest probability pd,kmax among the probabilities pD,0, . . . , pD,ν(D)−1, where kmax∈{0, 1, . . . , ν(D)−1}, and
the controller is configured to obtain a shortest difference vector t(BD, d) between t(D−1)−dD,kmax and a lattice L(BD), output the difference vector t(BD, d) as a difference vector t(d) and output a closest vector t(BD, c)=t−t(BD, d)∈L(BD) as a closest vector t(c) when a length of the difference vector t(BD, d) is smaller than a reference value, execute control of setting D+1 as a new D and further setting t(D)=t(D−1)−cD,kmax and of re-executing processes of the basis selector, the representative selector, the child node generator, the classical computer, the first quantum state generator, the second quantum state generator, the swap tester, the node selector, and the controller, when the length of the difference vector t(BD, d) is equal to or more than the reference value.

136 more elements

A computation apparatus receiving n-dimensional vectors aj and g and an integer N as inputs, and outputting (X1, . . . , Xm)T satisfying

(
a
11
⋯
a
1

m
a
21
⋯
a
2

m
a
31
⋯
a
3

m
⋮
⋱
⋮
a
n


1
⋯
a
nm
)

(
X
1
⋮
X
m
′
)

(
d
1
d
2
d
3
⋮
d
n
)


mod


N
=
(
g
1
g
2
g
3
⋮
g
n
)
processing circuitry configured to implement a first classical computer, a first quantum state generator, a second quantum state generator, a swap tester, a selector, and a second classical computer,
wherein n, n′, m and N are positive integers;
n′>n;
i=1, . . . , n;
i′=1, . . . , n′;
j=1, . . . , m;
im is an imaginary unit;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
<τ, χ> is an inner product of τ and χ;
η1⊆η2 represents that η1 is a subset of η2;
B={b1, . . . , bn} is a basis made up of linearly independent n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
L(B) is a lattice {Σi=1, . . . , n xibi|xi∈Z, bi∈B};
xi is an integer;
R⊆Zn′ is a partial region belonging to an n′-dimensional space made up of integer elements;
aj is an n-dimensional vector aj=(a1j, . . . , anj)T having n integer elements a1j, . . . , anj;
g is an n-dimensional vector g=(g1, . . . , gn)T having n elements g1, . . . , gn;
d is an n-dimensional vector d=(d1, . . . , dn)T having n elements d1, . . . , dn;
and εu is an n-dimensional unit vector εu=(0, . . . , 1, 0, . . . , 0)T where a u-th element is 1 and other elements are 0,
each of X1, . . . , Xm is obtained by a process corresponding to any D=1, . . . , m, Xj obtained by the process corresponding to the depth D is Xj(D)∈{X1, . . . , Xm}, a value of Xj(D) obtained by the process corresponding to the depth D is a jj(D), the n-dimensional vector aj corresponding to Xj obtained by the process corresponding to the depth D is aj(D)∈{a1, . . . , am}, AD−1=(aj(D) aj(D+1) . . . aj(m)), X′D−1=(Xj(D), Xj(D+), . . . , Xj(m))T, and
gD−1′=g−Σj′=1D−1αj(j′)aj(j′),
the first classical computer is configured to obtain a basis matrix βD of an LLL-reduced basis BD of a lattice defined by {aj(D+1)T aj(D+2)T . . . aj(m)T Nε1T . . . NεnT}, select the matrix αD which has integer elements of n columns and in which an Hermite normal form of a transposed matrix βD′T of a matrix βD′=(αD βD) obtained by arranging the matrix αD and the basis matrix βD in a horizontal direction is a matrix having diagonal elements of 1, obtain a unimodular matrix βD−′ satisfying βD−′βD′T=H for an Hermite normal form matrix H′, set a basis made up of row vectors bD,1′, . . . , bD,n′′ of the matrix βD′=(bD,1′, . . . , bD,n′′)T as BD′, set a basis made up of row vectors bD,1−′, . . . , bD,n′−′ of the unimodular matrix βD−′=(bD,1−′, . . . , bD,n′−′)T as BD−1, and obtain a target vector t(D)′=(t′D,1, . . . , t′D,n′)T∈span(BD′) having n′ integer elements t′D,i′ belonging to a space span(BD′) spanned by the basis BD′, in the process corresponding to the depth D,
Proj(t′D−1,j′)=(0, gD−1′T−j′•aj(D)T), Proj(μ) represents a projection onto an n′-dimensional vector space where first n′−n elements of μ are 0, L(B−′) is the lattice L(B−′)={Σi′=1, . . . , n′ xi′b−′i′|xi′∈Z, b−′i′∈B}, xi′ is an integer, and R⊆Zn′ is a partial region belonging to the n′-dimensional space made up of integer elements,
the first quantum state generator is configured to, in the process corresponding to the depth D, generate a plurality of registers in a quantum state

ϕ
〉
D
,
0
=
1

(
R
⋂
L

(
B
_
D
′
)
)


∑
x
∈
R
⋂
L

(
B
_
D
′
)


x
〉
,
the second quantum state generator is configured to perform quantum manipulation for one or some of the registers in a quantum state |ϕD,0 to cause a quantum state of the register(s) subjected to the quantum manipulation to transition to

ϕ
〉
t

(
D
,
j
′
)
=
1

(
R
⋂
L

(
B
_
D
′
)
)


∑
x
∈
R
⋂
L

(
B
_
D
′
)

e
2


π


i
m

〈
t
D
-
1
,
j
′
′
,
x
〉


x
〉
for j′=0, 1, 2, . . . , N−1, in the process corresponding to the depth D,
the swap tester is configured to execute a swap test for each pair of the register that stores the quantum state |ϕD,0 and the register that stores a quantum state |ϕt(D,j′) for j′=0, 1, 2, . . . , N−1, and decide whether a result of the swap test for the pair of the quantum state |ϕD,0 and the quantum state |ϕt(D,j′) is receipt or denied, in the process corresponding to the depth D,
the selector is configured to use a result of the swap test and compute a probability pD,j′ that a result of the swap test for the pair of the quantum state |ϕD,0 and the quantum state |ϕt(D,j′) is receipt, output, as aj(D), jmax∈{0, 1, 2, . . . , N−1} corresponding to a highest probability pD,jmax among the probabilities pD,0, pD,1, . . . , pD,N−1, and further output gD′=gD−1′−aj(D)•aj(D), in the process corresponding to the depth D, and
the second classical computer is configured to perform control of outputting (X1, . . . , Xm)T obtained by arranging αj(1), . . . , αj(m) when the selector outputs aj(D) for all D=1, . . . , m, and of re-executing processes of the first classical computer, the first quantum state generator, the second quantum state generator, the swap tester, the selector and the second classical computer when the selector does not output aj(D) for any D=1, . . . , m.

209 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/168,014Filed 23 Oct 2018
Priority: JP 2017-20501124 Oct 2017
Published: 27 Jun 2019
Term ends: Not estimatedThe source records don’t support an estimate.

Classification13 codes

G06N 10/60
Quantum computing, i.e. information processing based on quantum-mechanical phenomena: quantum algorithms, e.g. based on quantum optimisation,…
G06F 15/16
Digital computers in general ; Data processing equipment in general: combinations of two or more digital computers each having at least an…
G06F 17/14
Complex mathematical operations: fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization

Family

US 11,521,102 B2Related patent
US 2019/0197426 A1This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

patentgrep

Loading patent…

Abstract

A transformation apparatus receiving inputs of a basis B and a target vector t, and, outputting {rj1(c), rj1(d), rj0} and m, M and N that satisfy

(
(
r
11
(
c
)
…
r
1

n
(
c
)
r
21
(
c
)
…
r
2

n
(
c
)
r
31
(
c
)
…
r
3

n
(
c
)
⋮
⋱
⋮
r
m


1
(
c
)
…
r
mn
(
c
)
)
+
(
r
11
(
d
)
…
r
1

n
(
d
)
r
21
(
d
)
…
r
2

n
(
d
)
r
31
(
d
)
…
r
3

n
(
d
)
⋮
⋱
⋮
r
m


1
(
d
)
…
r
mn
(
d
)
)
)

(
t
1
(
d
)
⋮
t
n
(
d
)
)
+
(
e
1
e
2
e
3
⋮
e
m
)

mod


N
=
(
round

(
r
10

N
M
)
round

(
r
20

N
M
)
round

(
r
30

N
M
)
⋮
round

(
r
m


0

N
M
)
)
comprising processing circuitry configured to implement a first classical computer, a quantum state generator, a first quantum Fourier transformation unit, a manipulator, a first observer, a second quantum Fourier transformation unit, a second observer, an inverse quantum Fourier transformation unit, a third observer, and a second classical computer,
wherein n, m, M and N are positive integers;
M<N;
i=1, . . . , n;
j=1, . . . , m;
ηT is a transpose of η;
|Λ| is the number of elements of Λ;
round(μ) is an integer closest to μ;
floor(μ) is a maximum integer equal to or less than μ;
ceil(μ) is a minimum integer equal to or more than μ;
det(η) is a determinant of η;
B={b1, . . . , bn} is a basis made up of linearly independent n n-dimensional vectors bi;
each of the n-dimensional vectors bi has n integer elements;
β is a basis matrix that has n rows and n columns and includes, as elements, the n-dimensional vectors b1, . . . , bn of the basis B;
t=(t1, . . . , tn)T is a target vector having n integer elements ti;
xi is an integer;
L(B) is a lattice {Σi=1, . . . n xibi|xi∈Z, bi∈B};
τ is an n-dimensional vector;
τ+L(B)=L(B)+τ={τ+χ|χ⊂L(B)};
rji(c), rji(d), rj0 and ej are integers;
t(d) is a difference vector t(d)=t−t(c)=(t1(d), . . . , tn(d))T between the target vector t and a closest vector t(c)∈L(B) of the target vector t;
and s is an n-dimensional vector having integer elements,
the first classical computer is configured to select a multiple N of a least common multiple N′ of denominators of elements of an inverse matrix β−1 of the basis matrix β, and to obtain a dual basis B−={(N/N′)b1′, . . . , (N/N′)bn−′} of modulo N, for a dual basis B−′={b1−′, . . . , bn−′} of the basis B of modulo N′,
the quantum state generator is configured to set a quantum state of a register string that includes an index register having ceil(log2(M+1)) quantum bits, a data register having n×ceil(log2(N+1)) quantum bits, and a work register having n×ceil(log2(det(β)+1)) quantum bits to
1

B
R


∑
x
∈
B
R


0
〉


x
〉


0
〉
where BR is a set of points included in [0,N)n,
the first quantum Fourier transformation unit is configured to execute M-dimensional quantum Fourier transform on the index register, and to transform the quantum state of the register string into
1
M


B
R


∑
w
=
0
M
-
1

∑
x
∈
B
R


w
〉


x
〉


0
〉
the manipulator is configured to execute quantum manipulation of changing a quantum state |w|x|0 to a quantum state |w|x|det(β)(yw,x,1−floor(yw,x,1)), . . . , det(β)(yw,x,n−floor(yw,x,n)), on the register string in the quantum state obtained by the first quantum Fourier transformation unit, where x−wt=yw,x,1b1+ . . . +yw,x,nbn is satisfied,
the first observer is configured to observe the work register that stores the quantum state obtained by the manipulator, and to change the quantum states of the index register and the data register to
1
M

∑
w
=
0
M
-
1

(
1

B
R
⋂
(
L

(
B
)
+
s
+
wt
(
d
)
)


∑
x
∈
B
R
⋂
(
L

(
B
)
+
s
+
wt
(
d
)
)


w
〉


x
〉
)
the second quantum Fourier transformation unit is configured to execute N-dimensional quantum Fourier transform on the data register that stores the quantum state after observation by the first observer,
the second observer is configured to observe the data register that stores the quantum state obtained by the second quantum Fourier transformation unit to obtain an observation result (rj1, . . . , rjn),
the inverse quantum Fourier transformation unit is configured to execute M-dimensional inverse quantum Fourier transform on the index register that stores the quantum state after observation by the second observer,
the third observer is configured to observe the index register that stores the quantum state obtained by the inverse quantum Fourier transformation unit to obtain an observation result rj0, and
the second classical computer is configured to receive, as inputs, the dual basis B− obtained by the first classical computer, and the observation results (rj1, . . . , rjn) and rj0 obtained by performing processes of the quantum state generator, the first quantum Fourier transformation unit, the manipulator, the first observer, the second quantum Fourier transformation unit, the second observer, and the third observer, for j=1, . . . , m, and to obtain a closest vector rj(c)=(rj1(c), . . . , rjn(c))∈L(B−) of an n-dimensional vector rj=(rj1, . . . , rjn), and a difference vector rj(d)=rjrj(c)=(rj1(d), . . . , rjn(d)), for a dual lattice L(B−)={Σi−1, . . . , n xib−i|xi∈Z, b−i∈B−} and the n-dimensional vector rj.

341 more elements

Facts

Application

16/168,014Filed 23 Oct 2018

Priority

JP 2017-20501124 Oct 2017

Published

27 Jun 2019

Term ends

Not estimatedThe source records don’t support an estimate.

Classification13 codes

G06N 10/60
Quantum computing, i.e. information processing based on quantum-mechanical phenomena: quantum algorithms, e.g. based on quantum optimisation,…
G06F 15/16
Digital computers in general ; Data processing equipment in general: combinations of two or more digital computers each having at least an…
G06F 17/14
Complex mathematical operations: fourier, Walsh or analogous domain transformations , e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
G06F 17/16
Complex mathematical operations: matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization