Method for searching minimum

1 . A processor-implemented method for searching a minimum in N (N being a natural number) pieces of data, the method comprising:

determining a threshold;

initializing Qubits into a superposition state of indexes representing addresses in which each of the N pieces of data are recorded, and the threshold, which yields superposition-state data;

returning, from a superposition-state index, the superposition-state data corresponding to the superposition-state index through a quantum memory comprising a quantum random access memory (QRAM);

comparing the superposition-state data with the threshold in parallel through a quantum comparator (Q-comp) and the QRAM; and

searching the minimum based on the comparison result, wherein the searching of the minimum based on the comparison result comprises:

repeatedly performing an operation of writing an index related to data smaller than the threshold in a database, inverting a phase of a written state, and amplifying a probability of the written state through a Grover operator at a predetermined number of times;

returning an index measured as the repeated performing result;

updating the threshold by using the returned index related data when the returned index related data is smaller than the threshold;

repeatedly performing the minimum searching method by using the updated threshold; and

repeatedly performing the minimum searching method for a predetermined time τ th ;

returning the measured index when repeatedly performing the minimum searching method for the predetermined time τ th ; and

determining the returned index related data as the minimum when the returned index related data is smaller than the threshold,

wherein a quantum circuit is used to modularize the searching of the minimum into one computing device.

2 . The method of claim 1 , wherein the searching the minimum based on the comparison result comprises:

repeatedly performing an operation of writing an index related to data smaller than the threshold in a database, inverting a phase of a written state, and amplifying a probability of the written state through a Grover operator at a predetermined number of times;

returning an index measured as the repeated performing result; and

repeatedly performing the minimum searching method by using the threshold when the returned index related data is larger than the threshold.

3 . The method of claim 2 , further comprising:

repeatedly performing the minimum searching method for a predetermined time τ th .

4 . The method of claim 1 , wherein the predetermined time τ th is determined according to an equation τ th =1.25π√{square root over (N)}+1.4(log 2 N) 2 .

5 . The method of claim 1 , further comprising:

returning the measured index when repeatedly performing the minimum searching method for the predetermined time τ th ; and

determining the threshold related data as the minimum when the returned index related data is larger than the threshold.

6 . The method of claim 3 , wherein the predetermined time τ th is determined according to an equation τ th =1.25π√{square root over (N)}+1.4(log 2 N) 2 .

7 . The method of claim 3 , further comprising:

returning the measured index when repeatedly performing the minimum searching method for the predetermined time τ th ; and

determining the returned index related data as the minimum when the returned index related data is smaller than the threshold.

8 . The method of claim 3 , further comprising:

returning the measured index when repeatedly performing the minimum searching method for the predetermined time τ th ; and

determining the threshold related data as the minimum when the returned index related data is larger than the threshold.

9 . The method of claim 1 , wherein the determining a threshold includes determining any one of the N pieces of data as the threshold.

10 . The method of claim 1 , wherein the predetermined number of times is determined according to an equation O(√{square root over (N)}), and

wherein the O is a function representing time complexity according to an asymptotic notation.

11 . The method of claim 2 , wherein the predetermined number of times is determined according to an equation O(√{square root over (N)}), and

wherein the O is a function representing time complexity according to an asymptotic notation.

12 . The method of claim 1 , wherein the repeatedly performing an operation of writing an index related to data smaller than the threshold in a database, inverting a phase of a written state, and amplifying a probability of the written state through a Grover operator at a predetermined number of times, based on the comparison result includes, amplifying a probability of a state having an amplitude smaller than an average amplitude.

13 . The method of claim 2 , wherein the repeatedly performing an operation of writing an index related to data smaller than the threshold in a database, inverting a phase of a written state, and amplifying a probability of the written state through a Grover operator at a predetermined number of times, based on the comparison result includes, amplifying a probability of a state having an amplitude smaller than an average amplitude.

14 . The method of claim 1 , wherein the comparing the superposition-state data with the threshold in parallel through a quantum comparator (Q-comp) comprises:

recognizing whether a carry bit is generated by performing an addition operation of the threshold and a complement of the superposition-state data; and

comparing sizes of the superposition-state data and the threshold based on whether the carry bit is generated.

15 . The method of claim 14 , wherein the comparing sizes of the superposition-state data and the threshold based on whether the carry bit is generated comprises:

recognizing that the threshold is larger than the superposition-state data when it is recognized that the carry bit is generated.

16 . The method of claim 14 , wherein the comparing sizes of the superposition-state data and the threshold based on whether the carry bit is generated comprises:

recognizing that the superposition-state data is larger than the threshold when it is recognized that the carry bit is not generated.