WO2024052890A1 - Quantum annealing-based method and apparatus for computing solutions to problems - Google Patents

Abstract

A quantum annealing-based method for computing solutions to problems according to an embodiment of the present specification comprises analyzing a prepared problem statistically and holding constant a particular qubit value.

Description

Method and apparatus for calculating a solution to a problem based on quantum annealing

The present invention relates to a method and device for calculating a solution to a problem using a quantum computer.

Quantum annealing is mainly used for binary combinatorial optimization, and a superconductor-based quantum annealer that practically implements the Ising Model is used. However, due to technical limitations, it is difficult to initialize and manipulate each qubit that makes up the easing model, and the resulting errors do not accurately calculate the model programmed by the user, resulting in inaccurate results. Therefore, several methodologies are being proposed to correct these errors.

The technical problem to be achieved by the present invention is to eliminate repetitive encoding of qubits in order to compensate for the problems of prior technologies, while also eliminating the problem expected from a quantum annealer. The goal is to reduce the size of a given problem based on statistical analysis between repetitive post-processing tasks to maintain the gain in computational complexity.

The technical problem of the present invention is not limited to the technical problem described above, and other technical problems can be inferred from the embodiments of the present invention.

The present invention provides a method and device for calculating a solution to a problem based on quantum annealing.

As an aspect of the present invention, a method of calculating a solution to a problem based on quantum annealing includes a sample set including a plurality of qubits through quantum annealing. ) Obtaining; fixing the value of a specific qubit among the plurality of qubits based on statistical analysis; and calculating a solution to the problem based on the fixed specific qubit value. A solution calculation method is provided, including:

In another aspect of the present invention, an apparatus for calculating a solution to a problem based on quantum annealing, comprising: at least one processor; and at least one memory operably connected to the at least one processor and storing instructions that, when executed, cause the at least one processor to perform a specific operation. , wherein the specific operations include: an apparatus for calculating a solution to a problem based on quantum annealing, comprising: at least one processor; and at least one memory operably connected to the at least one processor and storing instructions that, when executed, cause the at least one processor to perform a specific operation. It includes, and the specific operation includes: obtaining a sample set including a plurality of qubits through quantum annealing; fixing the value of a specific qubit among the plurality of qubits based on statistical analysis; and calculating a solution to the problem based on the fixed specific qubit value. A solution calculation device comprising a is provided.

In another aspect of the present invention, a computer-readable non-volatile storage medium including at least one computer program that causes at least one processor to perform an operation, the operation being: a plurality of qubits through quantum annealing. Obtaining a sample set including: fixing the value of a specific qubit among the plurality of qubits based on statistical analysis; and calculating a solution to the problem based on the fixed specific qubit value. A storage medium containing a is provided.

In the methods and devices, the size of the problem can be reduced based on the value of the specific fixed qubit.

In the methods and devices, for the reduced size problem, the acquisition and fixation can be performed iteratively.

In the methods and devices, the statistical analysis may include analyzing the effect of the bias of each of the qubits on the state of system energy.

In the methods and devices, the statistical analysis includes: counting whether each of the qubits in the sample set has a value of 0 or 1; estimating the optimal value of the qubits by deriving a bias of whether each of the qubits is biased toward 0 or 1; and calculating an influence on the state of system energy for a specific qubit whose bias is greater than or equal to a threshold, and based on the calculation result of the influence, the value of the specific qubit may be fixed.

In the methods and devices, the bias can be derived by dividing the count value of each of the qubits by the number of the entire sample set.

In the methods and devices, the impact can be calculated by comparing the system energy value when the value of the specific qubit is 0 and the system energy value when the value of the specific qubit is 1. there is.

In the methods and devices, the statistical analysis may be performed on combinations of some of the qubits.

The solution calculation device may include a quantum computer.

The above-described aspects of the present invention are only some of the preferred embodiments of the present invention, and various embodiments reflecting the technical features of the present invention can be understood by those skilled in the art. It can be derived and understood based on the explanation.

According to one embodiment of the present invention, the optimal value of each qubit is estimated through high-level simple annealing result analysis without the need to identify the root cause of errors in the quantum annealer, while simultaneously reducing the size of the problem. , qualitative improvement in the results of repeated annealing operations can be expected.

The technical effects of the present invention are not limited to the above-described technical effects, and other technical effects can be inferred from the embodiments of the present invention.

Figure 1 illustrates scenarios of NTN to which a terminal can connect.

Figure 2 is a block diagram showing the main configuration of the solution calculation device.

Figure 3 is a flowchart showing a solution calculation method according to an embodiment of the present invention.

In order to make the characteristics and advantages of the problem-solving means of the present invention clearer, the present invention will be described in more detail with reference to specific embodiments of the present invention shown in the attached drawings.

However, detailed descriptions of known functions or configurations that may obscure the gist of the present invention are omitted in the following description and attached drawings. Additionally, it should be noted that the same components throughout the drawings are indicated by the same reference numerals whenever possible.

Terms or words used in the following description and drawings should not be construed as limited to their usual or dictionary meanings, and the inventor may appropriately define the concept of the term to explain his or her invention in the best way. It must be interpreted with meaning and concept consistent with the technical idea of the present invention based on the principle that it is. Therefore, the embodiments described in this specification and the configurations shown in the drawings are only one of the most preferred embodiments of the present invention, and do not represent the entire technical idea of the present invention, so at the time of filing the present application, various alternatives may be used to replace them. It should be understood that equivalents and variations may exist.

Additionally, unless otherwise defined, all terms used herein, including technical or scientific terms, have the same meaning as generally understood by a person of ordinary skill in the technical field to which the present invention pertains. Terms defined in commonly used dictionaries should be interpreted as having a meaning consistent with the meaning in the context of the related technology, and should not be interpreted in an ideal or excessively formal sense unless explicitly defined in the present application. No.

In addition, terms containing ordinal numbers, such as first, second, etc., are used to describe various components, and are used only for the purpose of distinguishing one component from other components and to limit the components. Not used. For example, the second component may be referred to as the first component without departing from the scope of the present invention, and similarly, the first component may also be referred to as the second component.

Additionally, the terms used in this specification are only used to describe specific embodiments and are not intended to limit the present invention. Singular expressions include plural expressions unless the context clearly dictates otherwise. In addition, terms such as "comprise" or "have" used in the specification are intended to indicate the presence of features, numbers, steps, operations, components, parts, or combinations thereof described in the specification, but are intended to indicate the presence of one or more of the features, numbers, steps, operations, components, parts, or combinations thereof described in the specification. It should be understood that this does not exclude in advance the presence or addition of other features, numbers, steps, operations, components, parts, or combinations thereof.

Additionally, terms such as “unit,” “unit,” and “module” used in the specification refer to a unit that processes at least one function or operation, and may be implemented as hardware, software, or a combination of hardware and software. In addition, the terms "a or an", "one", "the", and similar related terms are used in the context of describing the invention (particularly in the context of the claims below) as used herein. It may be used in both singular and plural terms, unless indicated otherwise or clearly contradicted by context.

In various examples of this disclosure, “/” and “,” should be interpreted as indicating “and/or.” For example, “A/B” can mean “A and/or B.” Furthermore, “A, B” may mean “A and/or B.” Furthermore, “A/B/C” may mean “at least one of A, B and/or C.” Furthermore, “A, B, C” may mean “at least one of A, B and/or C.”

In various examples of this disclosure, “or” should be construed to indicate “and/or.” For example, “A or B” may include “only A,” “only B,” and/or “both A and B.” In other words, “or” should be interpreted as indicating “additionally or alternatively.”

In addition to the terms described above, specific terms used in the following description are provided to aid understanding of the present invention, and the use of these specific terms may be changed to other forms without departing from the technical spirit of the present invention.

Additionally, embodiments within the scope of the present invention include computer-readable media having or transmitting computer-executable instructions or data structures stored on the computer-readable media. Such computer-readable media may be any available media that can be accessed by a general-purpose or special-purpose computer system. By way of example, such computer-readable media may include RAM, ROM, EPROM, CD-ROM or other optical disk storage, magnetic disk storage or other magnetic storage, or in the form of computer-executable instructions, computer-readable instructions or data structures. It may be used to store or transmit certain program code means, and may include, but is not limited to, a physical storage medium such as any other medium that can be accessed by a general purpose or special purpose computer system. .

In addition, the present invention is applicable to personal computers, laptop computers, handheld devices, multiprocessor systems, microprocessor-based or programmable consumer electronics, network PCs, minicomputers, mainframe computers, mobile phones, PDAs, and pagers. It can be implemented in a network computing environment with various types of computer system configurations, including pagers, quantum computers, etc. The invention may also be practiced in distributed system environments where tasks are performed by both local and remote computer systems that are linked over a network via wired data links, wireless data links, or a combination of wired and wireless data links. In a distributed system environment, program modules may be located in local and remote memory storage devices.

Additionally, it will be understood that each block of the processing flow diagrams and combinations of the flow diagram diagrams may be performed by computer program instructions. These computer program instructions can be mounted on a processor of a general-purpose computer, special-purpose computer, or other programmable data processing equipment, so that the instructions performed through the processor of the computer or other programmable data processing equipment are described in the flow chart block(s). It creates the means to perform functions. These computer program instructions may also be stored in computer-usable or computer-readable memory that can be directed to a computer or other programmable data processing equipment to implement a function in a particular manner, so that the computer-usable or computer-readable memory It is also possible to produce manufactured items containing instruction means that perform the functions described in the flowchart block(s). Computer program instructions can also be mounted on a computer or other programmable data processing equipment, so that a series of operational steps are performed on the computer or other programmable data processing equipment to create a process that is executed by the computer, thereby generating a process that is executed by the computer or other programmable data processing equipment. Instructions that perform processing equipment may also provide steps for executing the functions described in the flow diagram block(s).

Additionally, each block may represent a module, segment, or portion of code that includes one or more executable instructions for executing specified logical function(s). Additionally, it should be noted that in some alternative execution examples it is possible for the functions mentioned in the blocks to occur out of order. For example, it is possible for two blocks shown in succession to be performed substantially at the same time, or it is possible for the blocks to be performed in reverse order depending on the corresponding function.

In describing the embodiments of the present disclosure in detail, the main focus will be on the example of a specific system, but the main point claimed in the present specification is that the scope disclosed in the present specification is applicable to other communication systems and services with similar technical background. It can be applied within a range that does not deviate significantly, and this can be done at the discretion of a person with skilled technical knowledge in the relevant technical field.

Now, a method and apparatus for calculating a solution to a problem based on quantum annealing according to an embodiment of the present invention will be described in detail with reference to the drawings.

First, we will briefly describe the solution calculation method according to an embodiment of the present invention.

A qubit (or quantum bit) is the basic unit of information in quantum computing. Binary bits are the basic information unit in conventional computing and represent either 0 or 1. On the other hand, qubits can implement a linear combination of two states using quantum mechanical phenomena. A qubit can represent an arbitrary ratio of 0 and 1 by overlapping two states: a state with a certain probability of being 0 and a state with a certain probability of being 1. For example, a qubit may represent a state in which the probability of being 0 is 3/10 and the probability of being 1 is 7/10. Qubits can be implemented through trapped ions, photons, artificial or real atoms, quasiparticles, etc.

Quantum annealing effectively solves optimization problems that require finding the maximum (or minimum) value in the shortest possible time. ‘Hill-climbing’ in traditional computing is an approach that identifies a local maximum by repeatedly changing parameters to find a slightly better solution than the current solution. The problem is that the 'local maximum' found here may not be the closest value to the target (global maximum). Quantum annealing, on the other hand, provides a way to reach the goal by jumping to another, higher hill. The name quantum annealing comes from a classical computing technique called simulated annealing. The approaches are similar, but the difference is that quantum annealing uses physical quantum phenomena while simulated annealing uses random numbers to find higher hills to climb.

For a specific example, the quantum annealer may include a metal ring produced by processing metal niobium (Nb). Multiple rings are used for the quantum annealer. Depending on the direction of the current flowing through the metal ring, the qubit value expressed through the metal ring can be 1 or 0. For example, if the current flows counterclockwise, the qubit value may be 1, and if the current flows clockwise, the qubit value may be 0.

When the temperature of the metal ring reaches absolute zero, the metal ring becomes a superconductor, and current flows in both directions, allowing a superimposed state of 0 and 1 to be expressed.

When metal rings are overlapped and a magnetic field is applied in the transverse direction, the temperature of the metal rings rises and the superconductor effect is lost. Afterwards, as the magnetic field gradually weakens, interaction between each metal ring occurs. Depending on the interaction between each metal ring, current flows through each metal ring in either a clockwise or counterclockwise direction. By controlling the interaction between each metal ring, the current direction for each metal ring can be adjusted. The more metal rings with current flowing in the same direction, the higher the signal measured.

By repeating signal measurements while changing the combination of interactions between metal rings, an optimized combination can be derived.

Quantum annealer is one of the heuristic methodologies used in combinatorial optimization. Heuristics or heuristics are simple reasoning methods designed to quickly arrive at an answer in situations where a rational judgment cannot be made due to insufficient time or information, or where a systematic and rational judgment is not necessary. .

Compared to existing classical annealing methods, quantum annealers use the quantum tunnel effect to find the ground state energy of a given system. In the present invention, the quantum annealer may be a quantum annealing module implemented in program form within a specific device. Alternatively, the quantum annealer may be a separate device connected to the solution calculation device according to an embodiment of the present invention. When using the quantum tunnel effect, benefits can be expected compared to several methodologies, including classical annealing. However, due to current technological limitations, it is difficult to maximize the performance of quantum annealers.

Errors may occur in quantum annealers for a variety of complex reasons, such as noise in the external environment, quantum coherence phenomenon, limitations in connectivity between qubits within the annealer, and limitations in qubit manipulation precision. It can happen. Due to errors, the quantum annealer outputs inaccurate results that are different from what the user initially programmed and intended.

In practice, there are many difficulties in identifying and resolving all error factors. Through the method presented in the present invention, we aim to alleviate errors in the results of quantum annealing in a simple way at a high level.

In addition, heuristic methodologies, including quantum annealing, by their nature calculate the same problem repeatedly to derive an answer close to the optimal solution, but the larger the size of the problem, the greater the obstacle to the repetitive calculation process.

The core of the present invention is to gradually reduce the size of the problem by estimating the optimal value of the qubit through statistical analysis of quantum annealing results and then fixing the value of the qubit during the iterative annealing process.

Through the method of the present invention, the size of the problem is gradually reduced during the iterative calculation process, and as a result, the search space of the quantum annealer is reduced, thereby improving not only the gain in calculation time but also the quality of calculation results.

Hereinafter, a solution calculation method according to an embodiment of the present invention will be described with reference to FIG. 1.

Referring to FIG. 1, for a problem H to be solved, a solution calculation device (hereinafter abbreviated as device) performs sampling using a quantum annealer and obtains a set of n samples. For example, n rows in Figure 1 correspond to a set of n samples. Excluding omitted portions, FIG. 1 shows five sample sets as examples.

Afterwards, the device counts whether each qubit in the entire sample set has a value of 0 or 1. Referring to FIG. 1, within the range shown, the first qubit among n samples has 5 1 values, and the second qubit has 2 1 values and 3 0 values. The third and fourth qubits each have three 1 values and two 0 values. The fifth qubit has five zero values.

The device divides the count value of each qubit by the number of the entire sample set, determines whether the qubit is statistically biased toward 0 or 1, and estimates the optimal value of the qubit. For example, in the case of the first qubit, the value of 5 of the 5 sample sets is 1, so by dividing the count value of 5 by 5, it is confirmed that the statistical bias for the qubit value of 1 is 1. Likewise, it is confirmed that the statistical bias toward 0 of the qubit value of the first qubit is 0. In the case of the second qubit, since it has two 1 values, if the count value 2 is divided by the number of sample sets 5, it is confirmed that the bias of the qubit value for 1 is 2/5. In the case of the fifth qubit, 0 1 values are counted, so if the count value 0 is divided by 5, it is confirmed that the bias toward 1 in the qubit value is 0.

The device sets a threshold and, if the bias of each qubit is greater than the threshold, calculates the impact of the qubit on the state of the overall system energy. The threshold may be set, for example, to a bias of 1 versus 0 or 1. Referring to Figure 1, the first and fifth qubits correspond to qubits that are above the threshold.

The device fixes the value of the qubit whose bias is greater than the threshold if its influence on the system energy approaches the energy of the ground state. In other words, the value of the qubits whose bias is above the threshold is fixed based on the calculation result of the effect on the system energy of the qubits whose bias is above the threshold. Specifically, the impact of a specific qubit with a bias greater than a threshold on the system energy can be calculated by comparing the system energy value when the specific qubit is 0 and the system energy value when the specific qubit is 1.

For example, the effect of the first qubit on the system energy among the first and fifth qubits in Figure 1 is the system energy value when the first qubit is 0 and the system energy value when the first qubit is 1. It can be calculated through comparison. If the system energy value when the first qubit is 0 is less than the system energy value when the first qubit is 1, there is an error, so the value of the first qubit is not fixed to 1. If the system energy value when the first qubit is 1 is less than the system energy value when the first qubit is 0, the value of the first qubit is fixed to 1.

Likewise, the fifth qubit can be calculated by comparing the system energy value when the fifth qubit is 0 and the system energy value when it is 1. If the system energy value when the fifth qubit is 0 is less than the system energy value when the fifth qubit is 1, the value of the fifth qubit is fixed to 1. If the system energy value when the fifth qubit is 1 is less than the system energy value when the fifth qubit is 0, there is an error, so the value of the fifth qubit is not fixed to 0.

The device reduces the size of the problem based on fixed qubit values. Referring to Figure 1, qubits fixed in problem H can be reflected in the problem in the form of offsets.

The device repeats the entire process with additional annealing.

Above, the solution calculation method according to an embodiment of the present invention has been described with reference to FIG. 1.

In this specification, when the value of a qubit is fixed through a series of processing processes within an acquired sample set, the processing process may be referred to as statistical analysis.

The optimal value of the qubit derived during the process described with reference to FIG. 1 may correspond to a solution to the problem. As the number of qubits fixed through repetition increases, the size of the problem, that is, the search space to be searched by the quantum annealer, decreases, the time required to estimate the optimal value of the qubits decreases, and the accuracy of the optimal value increases. It can be.

In addition, the device can not only estimate the optimal value of a single qubit, but also estimate the optimal value of the combination by looking at statistical patterns in the form of combinations/clusters of qubits. When the device analyzes the form of the combination of qubits, it is expected that quantum entanglement within the system can be inferred through additional analysis.

For example, the device counts what combinations of qubits look like in the entire sample set.

When the combination of qubits is set as a unit of two combinations, the device can count whether the combination of qubits belongs to 00, 01, 10, or 11. For example, for the combination of the first two qubits in Figure 1, two 11 combinations and three 10 combinations are counted.

When the combination of qubits is set in units of three combinations, the device can count which of 000, 001, 010, 011, 100, 101, 110, and 111 the combination of qubits belongs to. For example, for the combinations of the first three qubits in Figure 1, one 110 combination, two 101 combinations, one 111 combination, and one 100 combination are counted.

The device can determine the values of the qubits by performing statistical analysis based on the combination of qubits.

Above, the solution calculation method according to an embodiment of the present invention has been described. Hereinafter, solution calculation autonomy according to an embodiment of the present invention will be described with reference to FIG. 2.

FIG. 2 is a block diagram showing the main configuration of the solution calculation device 300.

Referring to FIG. 2, the solution calculation device 300 according to the present invention includes an input module 310, an output module 330, a quantum annealing module 350, a storage module 370, and a control module 390. It can be configured.

The input module 310 receives various information such as voice and/or text information, and transmits signals input in relation to setting various functions and controlling functions of the solution calculation device 300 to the control module 390. In addition, the input module 310 may be configured to include at least one of a keypad and a touchpad that generate an input signal according to the user's touch or manipulation, and/or a microphone that generates an input signal for a voice according to the user's utterance. . At this time, the input module 310 is configured in the form of a touch panel (or touch screen) together with the output module 330 and can perform input and display functions simultaneously. Additionally, the input module 310 may use any type of input means that may be developed in the future, in addition to input devices such as a keyboard, keypad, mouse, joystick, etc. In particular, the input module 310 according to the present invention detects input information input from the user and transmits it to the control module 390.

In particular, in the present invention, the solution calculation device 300 can receive a problem for which a solution must be calculated through the input module 310.

The output module 330 displays information about a series of operation states and operation results that occur while the solution calculation device 300 performs its functions. Additionally, the output module 330 may display menus of the solution calculation device 300 and user data input by the user. Here, the output module 390 includes a liquid crystal display (LCD), an ultra-thin film transistor LCD (TFT-LCD), a light emitting diode (LED), and an organic light emitting diode (OLED). Organic LED), active organic light emitting diode (AMOLED, Active Matrix OLED), Retina Display, flexible display, and 3 Dimensional display. Additionally, the output module 390 may include a speaker that outputs an electrical signal in the form of sound. At this time, when the output module 330 is configured in the form of a touch screen, the output module 330 may perform some or all of the functions of the input module 310.

In particular, in the present invention, the solution calculation device 300 can display the derived solution using graphics, text, sound, etc. in a form that can be recognized by the user through the output module 330.

The quantum annealer module 350 is a module for performing the function of the quantum annealer described above. The quantum annealer module 350 may perform quantum annealing on the problem input through the input module 310 to form a sample set.

The storage module 370 is a device for storing data, includes a main memory and an auxiliary memory, and stores application programs necessary for the functional operation of the solution calculation device 300. The storage module 370 includes random access memory (RAM), dynamic RAM (DRAM), read only memory (ROM), flash memory, volatile memory, and non-volatile memory. and/or a combination thereof. This storage module 370 may largely include a program area and a data area. Here, when the solution calculation device 300 activates each function in response to the user's request, it executes the corresponding application programs under the control of the control module 390 to provide each function.

The storage module 370 according to the present invention can store an operating system that boots the solution calculation device 300, various application programs, user information matching the solution calculation device 300, etc. In particular, the storage module 370 according to the present invention can store a solution calculation program 371 for providing the solution calculation method according to the present invention.

The control module 390 may be a process device that drives an operating system (OS) and each component. For example, control module 390 may be comprised of one or more processor sets. Additionally, the control module 390 may be composed of a set of a communication control processor, an application processor, an electronic control unit (ECU), a graphics processing processor, and a memory control processor.

The control module 390 controls the signal received through the input module 310 to be processed through one or more combinations of the operations described in FIG. 1 and output through the output module 330, and the signals generated in this process are controlled. Information or data can be controlled to be stored in the storage module 370.

Although not shown, the solution calculation device 300 may further include a communication module. The communication module (not shown) includes an RF transmitting means that up-converts and amplifies the frequency of the transmitted signal, an RF receiving means that amplifies the received signal to low noise and down-converts the frequency, and data for processing a communication protocol according to a specific communication method. Including processing means, etc. This communication module (not shown) may include at least one of a wireless communication module (not shown) and a wired communication module (not shown). In addition, the wireless communication module is configured to transmit and receive data according to a wireless communication method, and when the solution calculation device 300 uses wireless communication, one of the wireless network communication module, wireless LAN communication module, and wireless fan communication module is used. Using this, the input problem and derived solution can be transmitted and received with an external device.

As previously described, the modules illustrated in FIG. 2 may be physically included in a single device. Additionally, in a distributed computing environment, each physically separated module may be configured to be connected wired/wireless.

Above, the configuration and operation method of the solution calculation device 300 according to the present invention have been described.

Hereinafter, we will look at the solution calculation method according to an embodiment of the present invention through a flowchart.

Figure 3 is a flowchart showing a solution calculation method according to an embodiment of the present invention.

Referring to FIG. 3, the solution calculation method according to an embodiment of the present invention is performed by the solution calculation device 300, and obtains a sample set including a plurality of qubits through quantum annealing (S501). , fixing the value of a specific qubit among a plurality of qubits based on statistical analysis (S503), and calculating a solution to the problem based on the fixed specific qubit value (S505). You can.

The sample set can be obtained through quantum annealing on a problem input by a user or a problem whose size has been reduced by the statistical analysis process of the present invention.

Statistical analysis may include a process of analyzing the effect of the bias of each qubit on the state of system energy, as previously described in relation to FIG. 1.

Specifically, the statistical analysis counts which value each of the qubits in the sample set has between 0 and 1, and derives the bias of which value each of the qubits is biased towards between 0 and 1. This may include estimating the optimal value of the qubits and calculating the effect on the state of the system energy for specific qubits whose bias is above a threshold.

The solution calculation device 300 fixes the value of a specific qubit based on a calculation result of the influence that a specific qubit with a bias greater than a threshold has on the state of system energy. The solution calculation device 300 determines the effect of a specific qubit with a bias equal to or greater than a threshold on the state of system energy by calculating the system energy value when the value of the specific qubit is 0 and the value of the specific qubit when the value is 1. It is calculated by comparing the system energy values in each case.

The solution calculation device 300 derives the bias by dividing the count value of each qubit by the number of the entire sample set.

The solution calculation device 300 can reduce the size of the problem by fixing the value of a specific qubit. The solution calculation device 300 performs quantum annealing on the problem of reduced size to obtain a second sample set, and performs statistical analysis on the obtained second sample set to fix the value of the second specific qubit. can do. By fixing the value of the second specific qubit, the size of the problem is further reduced. The solution calculation device 300 may repeatedly perform a series of processes, such as obtaining a third sample set for a problem whose size is further reduced.

The solution calculation device 300 may output the estimated optimal value as a solution when the size of the problem is reduced to a certain size or less or when the optimal value of the qubits is derived to be the same more than a certain number of times.

Above, the solution calculation method according to an embodiment of the present invention has been described through a flowchart.

Although not essential, the solution calculation device 300 may be connected to a terrestrial communication network through a communication module. Depending on how the system is implemented, the terrestrial communication network may use wired communication methods such as Ethernet, xDSL (ADSL, VDSL), HFC (Hybrid Fiber Coaxial Cable), FTTC (Fiber to The Curb), and FTTH (Fiber To The Home). WLAN (Wireless LAN), Wi-Fi, Wibro, Wimax, HSDPA (High Speed Downlink Packet Access), LTE (Long Term Evolution), LTE-A (Long Term Evolution Advanced) ), wireless communication methods such as NR (New RAT) can also be used.

In addition, this communication network includes, for example, a plurality of access networks (not shown) and a core network (not shown), and may be configured to include an external network, such as an Internet network (not shown). Here, the access network (not shown) is an access network that performs wired and wireless communication with the solution calculation device, for example, a number of base stations such as BS (Base Station), BTS (Base Transceiver Station), NodeB, eNodeB, gNodeB, and BSC. It can be implemented with a base station controller such as (Base Station Controller) or RNC (Radio Network Controller).

In addition, the core network (not shown) that constitutes the mobile network together with the access network (not shown) serves to connect the access network (not shown) with an external network, such as an Internet network (not shown).

This core network (not shown) is a network system that performs major functions for mobile communication services, such as mobility control and switching between access networks (not shown), and performs circuit switching or packet switching. and manages and controls packet flow within the mobile network. In addition, the core network (not shown) manages inter-frequency mobility and plays a role in linking traffic within the access network (not shown) and the core network (not shown) with other networks, such as the Internet network (not shown). It may be possible. This core network (not shown) further includes Serving GateWay (SGW), PDN GateWay (PGW), Mobile Switching Center (MSC), Home Location Register (HLR), Mobile Mobility Entity (MME), and Home Subscriber Server (HSS). It may be configured to include.

Additionally, the Internet network (not shown) refers to a typical open communication network, that is, a public network, in which information is exchanged according to the TCP/IP protocol.

Meanwhile, the memory mounted on each device of the present invention stores information within the device. In one implementation, the memory is a computer-readable medium. In one implementation, the memory may be a volatile memory unit, and in another implementation, the memory may be a non-volatile memory unit. In one implementation, the storage device is a computer-readable medium. In various different implementations, the storage device may include, for example, a hard disk device, an optical disk device, or some other mass storage device.

Although the specification and drawings describe example device configurations, implementations of the functional operations and subject matter described herein may be implemented in other types of digital electronic circuits, or may be implemented in the structures disclosed herein and their structural equivalents. It may be implemented as computer software, firmware, or hardware, or as a combination of one or more of these. Implementations of the subject matter described herein may relate to one or more computer program products, that is, computer program instructions encoded on a tangible program storage medium for controlling the operation of or execution by a device according to the invention. It can be implemented as the above modules. The computer-readable medium may be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter that affects a machine-readable radio wave signal, or a combination of one or more of these.

In addition, various information generated when executing the solution calculation method of the present invention may be stored and accessed in any computer-readable medium related to the computing system. For example, some of these program modules and some of the associated program data may be included in an operating system, application program, program module, and/or program data for storage in system memory.

Additionally, when a mass storage device, such as a hard disk, is connected to the computing system, these program modules and related program data may be stored in the mass storage device. In a network environment, program modules or portions thereof related to the present invention may be stored in a remote computer system connected through a network interface or a modem of the input/output interface. Execution of these modules can be performed in a distributed environment.

As described above, although this specification contains details of numerous specific implementations, these should not be construed as limitations on the scope of any invention or what may be claimed, but rather may be specific to particular embodiments of a particular invention. It should be understood as a description of features. Certain features described herein in the context of individual embodiments may also be implemented in combination in a single embodiment. Conversely, various features described in the context of a single embodiment can also be implemented in multiple embodiments individually or in any suitable sub-combination. Furthermore, although features may be described as operating in a particular combination and initially claimed as such, one or more features from a claimed combination may in some cases be excluded from that combination, and the claimed combination may be a sub-combination. It can be changed to a variant of a sub-combination.

Likewise, although operations are depicted in the drawings in a particular order, this should not be construed as requiring that those operations be performed in the specific order or sequential order shown or that all of the depicted operations must be performed to obtain desirable results. In certain cases, multitasking and parallel processing may be advantageous. Additionally, the separation of various system components in the above-described embodiments should not be construed as requiring such separation in all embodiments, and the described program components and systems may generally be integrated together into a single software product or packaged into multiple software products. You must understand that it is possible.

Specific embodiments of the subject matter described herein have been described. Other embodiments are within the scope of the following claims. For example, the operations recited in the claims can be performed in a different order and still achieve desirable results. As an example, the process depicted in the accompanying drawings does not necessarily require the specific depicted order or sequential order to achieve desirable results. In certain implementations, multitasking and parallel processing may be advantageous.

The present description sets forth the best mode of the invention and provides examples to illustrate the invention and to enable any person skilled in the art to make and use the invention. The specification prepared in this way does not limit the present invention to the specific terms presented. Accordingly, although the present invention has been described in detail with reference to the above-described examples, those skilled in the art may make modifications, changes, and variations to the examples without departing from the scope of the present invention.

Therefore, the scope of the present invention should not be determined by the described embodiments, but by the scope of the patent claims.

The present invention relates to a method and apparatus for calculating a solution to a problem based on quantum annealing. According to the present invention, when deriving a solution to a problem using a quantum computer, it is possible to derive a solution that is faster and more reliable than existing solutions through statistical analysis.

Therefore, the present invention can contribute to the development of related industries by providing a method and device for calculating a solution to a problem based on quantum annealing, and not only has sufficient marketability or commercial potential, but also can be clearly implemented in reality, so it can contribute to the industry. There is a possibility of availability.

Claims (24)

As a method of calculating a solution to a problem based on quantum annealing, Obtaining a sample set including a plurality of qubits through quantum annealing; fixing the value of a specific qubit among the plurality of qubits based on statistical analysis; and calculating a solution to the problem based on the fixed specific qubit value; Including, How to calculate the solution. According to paragraph 1, The size of the problem is reduced based on the value of the fixed specific qubit, How to calculate the solution. According to paragraph 2, For the reduced size problem, the acquisition and fixation are performed iteratively, How to calculate the solution. According to paragraph 1, The statistical analysis includes analyzing the effect of the bias of each of the qubits on the state of system energy, How to calculate the solution. According to paragraph 1, The above statistical analysis: Count whether each of the qubits in the sample set has a value of 0 or 1; estimating the optimal value of the qubits by deriving a bias of whether each of the qubits is biased toward 0 or 1; and calculating the effect on the state of system energy for a particular qubit where the bias is above a threshold, Based on the calculation result of the influence, the value of the specific qubit is fixed, How to calculate the solution. According to clause 5, The bias is derived through dividing the count value of each of the qubits by the number of the entire sample set, How to calculate the solution. According to clause 5, The influence is calculated by comparing the system energy value when the value of the specific qubit is 0 and the system energy value when the value of the specific qubit is 1. How to calculate the solution. According to paragraph 1, The statistical analysis is performed on combinations of some of the qubits, How to calculate the solution. In a device for calculating a solution to a problem based on quantum annealing, at least one processor; and at least one memory operably connected to the at least one processor and storing instructions that, when executed, cause the at least one processor to perform a specific operation; Including, The specific operations above are: Obtaining a sample set including a plurality of qubits through quantum annealing; fixing the value of a specific qubit among the plurality of qubits based on statistical analysis; and calculating a solution to the problem based on the fixed specific qubit value; Including, Solution calculation device. According to clause 9, The size of the problem is reduced based on the value of the fixed specific qubit, Solution calculation device. According to clause 10, For the reduced size problem, the acquisition and fixation are performed iteratively, Solution calculation device. According to clause 9, The statistical analysis includes analyzing the effect of the bias of each of the qubits on the state of system energy, Solution calculation device. According to clause 9, The above statistical analysis: Count whether each of the qubits in the sample set has a value of 0 or 1; estimating the optimal value of the qubits by deriving a bias of whether each of the qubits is biased toward 0 or 1; and calculating the effect on the state of system energy for a particular qubit where the bias is above a threshold, Based on the calculation result of the influence, the value of the specific qubit is fixed, Solution calculation device. According to clause 13, The bias is derived through dividing the count value of each of the qubits by the number of the entire sample set, Solution calculation device. According to clause 13, The influence is calculated by comparing the system energy value when the value of the specific qubit is 0 and the system energy value when the value of the specific qubit is 1. Solution calculation device. According to clause 9, The statistical analysis is performed on combinations of some of the qubits, Solution calculation device. A computer-readable, non-volatile storage medium comprising at least one computer program that causes at least one processor to perform operations, the operations comprising: Obtaining a sample set including a plurality of qubits through quantum annealing; fixing the value of a specific qubit among the plurality of qubits based on statistical analysis; and calculating a solution to the problem based on the fixed specific qubit value; Including, storage media. According to clause 17, The size of the problem is reduced based on the value of the fixed specific qubit, storage media. According to clause 18, For the reduced size problem, the acquisition and fixation are performed iteratively, storage media. According to clause 17, The statistical analysis includes analyzing the effect of the bias of each of the qubits on the state of system energy, storage media. According to clause 17, The above statistical analysis: Count whether each of the qubits in the sample set has a value of 0 or 1; estimating the optimal value of the qubits by deriving a bias of whether each of the qubits is biased toward 0 or 1; and calculating the effect on the state of system energy for a particular qubit where the bias is above a threshold, Based on the calculation result of the influence, the value of the specific qubit is fixed, storage media. According to clause 21, The bias is derived through dividing the count value of each of the qubits by the number of the entire sample set, storage media. According to clause 21, The influence is calculated by comparing the system energy value when the value of the specific qubit is 0 and the system energy value when the value of the specific qubit is 1. storage media. According to clause 17, The statistical analysis is performed on combinations of some of the qubits, storage media.

Images