Traveling salesman problem solution using magnonic combinatorial device

Scientific Reports volume 13, Article number: 11708 (2023) Cite this article

207 Accesses

Metrics details

Traveling salesman problem (TSP) is a decision-making problem that is essential for a number of practical applications. Today, this problem is solved on digital computers exploiting Boolean-type architecture by checking one by one a number of possible routes. In this work, we describe a special type of hardware for the TSP solution. It is a magnonic combinatorial device comprising magnetic and electric parts connected in the active ring circuit. There is a number of possible propagation routes in the magnetic mesh made of phase shifters, frequency filters, and attenuators. The phase shifters mimic cities in TSP while the distance between the cities is encoded in the signal attenuation. The set of frequency filters makes the waves on different frequencies propagate through the different routes. The principle of operation is based on the classical wave superposition. There is a number of waves coming in all possible routes in parallel accumulating different phase shifts and amplitude damping. However, only the wave(s) that accumulates the certain phase shift will be amplified by the electric part. The amplification comes first to the waves that possess the minimum propagation losses. It makes this type of device suitable for TSP solution, where waves are similar to the salesmen traveling in all possible routes at a time. We present the results of numerical modeling illustrating the TSP solutions for four and six cities. Also, we present experimental data for the TSP solution with four cities. The prototype device is built of commercially available components including magnetic phase shifters/filters, coaxial cables, splitters, attenuators, and a broadband amplifier. There are three examples of finding the shortest route between the cities for three different sets of city-to-city distances. The proposed approach is scalable to TSP with a larger number of cities. Physical limits and challenges are also discussed.

TSP is one of the most well-known combinatorial optimization problems1. It can be stated as follows: "Given a list of cities and the distances between each pair of cities, find the shortest possible route that visits each city exactly once and returns to the origin city." It is a non-deterministic polynomial-time hardness (NP-hard) problem which means that there is no guarantee to get the optimal route and no exact algorithm to solve it in polynomial time. TSP is important in a variety of practical applications including transportation2, scheduling3, and genomics4. Mathematically, it can be defined as given a set of \(n\) cities, named \(\left\{{c}_{1},{c}_{2},\dots ,{c}_{n}\right\}\), and permutations \(\left\{{\sigma }_{1},{\sigma }_{2},\dots ,{\sigma }_{n!}\right\}\). The objective is to choose \({\sigma }_{i}\) such that the sum of all Euclidean distances between cities in a tour is minimized. TSP can be modeled as an undirected weighted graph as shown in Fig. 1, where the cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's weight. TSP can be solved by checking one by one all possible \(\left(n-1\right)!/2\) possible routes. It is relatively easy to check all possible routes for a small number of cities. For example, there are \(\left(4-1\right)!/2=3\) routes for the TSP with four cities. The number of possible routes increases proportionally to \(n\) factorial which makes it difficult to solve for a large number of cities using classical computing devices.

Undirected weighted graph for TSP with four cities. The cities are the graph's vertices, paths are the graph's edges, and a path's distance is the edge's weight.

There were several attempts to build special hardware for TSP solution5,6. For instance, 6-city TSP was solved using a Kohonen-type optical network6. However, none of these approaches resulted in a practically viable device. Recently, a variety of optimization techniques used in artificial intelligence (AI) have been applied to TSP7. It may significantly speed up the TSP solution but cannot provide a fundamental advantage being implemented on conventional hardware.

Here, we consider a special type of combinatorial device in which an act of computation is associated with finding a propagation route of the wave through the selected nodes in the mesh. This approach was first described in Ref.8. The main idea is to exploit the advantage of classical wave superposition, where a number of waves can propagate through different routes at the same time. It may be possible to amplify only those signals that propagate through the selected sites in the mesh and accumulate a certain phase shift. Spin wave (magnonic) devices are most suitable for this purpose due to the prominent phase shifts that can be achieved in micrometer-length waveguides. The rest of the work is organized as follows. In “Material structure and principle of operation” section, we describe the principle of operation of the magnonic combinatorial logic device for TSP. The results of numerical modeling illustrating the TSP solution for four and six cities are presented in “Numerical modeling” section. The experimental data for the TSP solution for four cities are presented in “Experimental data” section. The Discussion and Conclusions are given in “Discussion” and “Conclusions” sections, respectively.

The schematics of the combinatorial device for TSP with four cities are shown in Fig. 2. The core of the structure is the mesh consisting of the phase shifters, attenuators, frequency filters, and power sensors. The circles marked with letters A, B, C, and D, are phase shifters representing the four cities. Each phase shifter provides a unique phase shift which is proportional to the logarithm of a prime number. For example, city A is represented by the phase shifter providing \(\pi \times \mathit{Log}\left(2\right)\) phase shift to the propagating signal. City B is represented by the phase shifter providing \(\pi \times \mathit{Log}\left(3\right)\) phase shift, and so on. There are two cities A, one on the left and one on the right sides of the mesh. This is the city the salesman starts from and should return to after the trip. The phase shifters are connected to each other via waveguides. There is an attenuator inserted into each waveguide. The distance between the cities is encoded into the signal attenuation. For example, 10 miles can be taken equivalent to 1 dB attenuation. There is a set of frequency bandpass filters. These filters are aimed to ensure different frequencies for different propagation routes from city A on the left to city A on the right. For example, only a signal with frequency \({f}_{1}\) can propagate through route A-B-A; only a signal with frequency \({f}_{2}\) can propagate through route A-B-C-A, etc. There is also a set of power detectors inserted into each waveguide. These detectors are aimed to provide the output: the signal propagation route. In Fig. 2, the detectors are marked as color circles. The green color is to depict the energy flow above some reference value (e.g., 1 dBm). The red color is to depict no energy flow.

Schematics of the combinatorial device for TSP with four cities. The core of the structure is the mesh consisting of the phase shifters, attenuators, frequency filters, and power sensors. The circles marked with letters A, B, C, and D, are phase shifters representing the four cities. Each phase shifter provides a unique phase shift which is proportional to the logarithm of a prime number. For example, city A is represented by the phase shifter providing \(\pi \times \mathit{Log}\left(2\right)\) phase shift to the propagating signal. City B is represented by the phase shifter providing \(\pi \times \mathit{Log}\left(3\right)\) phase shift, and so on. There are two cities A, one of the left and one of the right sides of the mesh. This is the city the salesman starts from and should return to after the trip. The phase shifters are connected to each via waveguides. There is an attenuator inserted between each pair of cities. The distance between the cities is encoded into the signal attenuation. For example, 10 miles can be taken equivalent to 1 dB attenuation. There is a set of frequency bandpass filters. These filters are aimed to ensure different frequencies for different propagation routes from the city A on the left to city A on the right.

There is a broadband amplifier \(G\), a voltage-tunable phase shifter \(\Psi\), and a voltage-tunable attenuator \(R\) outside the mesh. Hereafter, we refer to these elements as the “external” part. The broadband amplifier is to provide signal amplification for all signal frequencies. The voltage-tunable phase shifter and the voltage-tunable attenuator are to control the phase shift and the attenuation of the external part. The combination of the mesh with the external part constitutes a multi-path active ring circuit8. There is a number of possible routes for signals to propagate in the mesh. The different propagation paths are associated with different phase shift \(\Delta ({f}_{i})\) as well as the different signal attenuation \(L({f}_{i})\), where \({f}_{i}\) is the frequency of the signal propagating through the \(i\)-th route. There is a superposition of waves propagating through the different paths in the circuit. However, only some of the frequencies will be amplified to enable stable auto-oscillations. There are two conditions for auto-oscillations to occur in an active ring circuit9:

where \(G\) is the gain provided by the amplifier, \(R\) is the signal attenuation in the electric part, \(\Psi\) is the phase shift of the external electric part. The first Eq. (1) states the amplitude condition for auto-oscillations: the gain provided by the broadband amplifier should be sufficient to compensate for losses in the mesh and losses introduced by the external attenuator. The second equation states the phase condition for auto-oscillations: the total phase shift for a signal circulating through the ring should be a multiple of \(2\pi .\) In this case, signals come in phase every propagation round. A more rigorous description of signal propagation in active ring circuits can be found in Ref.9.

The computational procedure for TSP is the following. The external phase shifter \(\Psi\) is set up to the value

where the last term on the right is the sum of the phase delays for the selected cities. In our case of four cities,

Only signals propagating through the selected cities (e.g., A,B,C,D, and A) will be amplified as the total phase shift through the ring is \(2\pi\). Signals that propagate through the selected cities but more than ones (e.g., A-C-B-D-C-A) will not be amplified because the total phase shift is not a multiple of \(2\pi\). A more detailed explanation of the selective signal amplification in a multi-path active ring circuit can be found in Ref.8. All other signal propagating on other paths (e.g., A-B-A, A-C-D-A, etc.) won’t be amplified as the phase condition (2) is not satisfied.

Then, it is possible to find the shortest path (i.e., the path with minimum losses) using the external attenuator \(R\). There may be a number of routes for which the total phase shift satisfies Eq. (2). The number of routes satisfying the amplitude condition Eq. (1) decreases with the increase of the external damping \(R\). The shortest path will disappear the last as it may sustain the maximum external damping. There are two important points we want to emphasize regarding the principle of operation. The system starts with a superposition of all possible frequencies propagating through all possible paths. We can amplify only the signals coming through the selected nodes/cities using the external phase shifter to satisfy the phase condition (2). The shortest route is found then by introducing additional damping so only the signal with minimum losses can satisfy the amplitude condition (1). In the next section, we present the results of numerical modeling illustrating the TSP solution.

To illustrate the solution procedure described above, we present the results of numerical modeling for the four-cities TSP. In Fig. 3A, there is shown a map of the 20 most fun cities in U.S. (source WalletHub). The Traveling Salesman starts from Los Angeles and has to visit Miami, Washington, Chicago, and come back to Los Angeles. The distances between the cities are taken from the Google Map application. The problem is solved using the combinatorial device shown in Fig. 2. The distances between the cities are converted into signal attenuation (e.g., 1000 miles = 10 dB attenuation).

(A) U.S. map with the 20 most fun cities. The Traveling Salesman starts from Los Angeles and has to visit Miami, Washington, Chicago and come back to Los Angeles. (B) Results of numerical modeling showing the distances for all possible routes. The routes are marked by #1, #2, … #27. Each of the routes is associated with a continuous sinusoidal signal of some frequency \({f}_{1}\), \({f}_{2},\dots {f}_{27}\). (C) Results of numerical modeling showing phase shifts for all possible routes. Only 6 routes out of 27 satisfy the phase condition (2) and will be amplified. (D) Results of numerical modeling depicting the shortest route(s): Los Angeles–Miami–Washington–Chicago–Los Angeles and Los Angeles–Chicago–Washington–Miami–Los Angeles.

There are 27 possible routes between the four cities (e.g., Los Angles–Washington–Los Angeles–Miami–Washington–Los Angeles). In Fig. 3B, there are shown the travel distances for all routes. The routes are marked by #1, #2, … #27. Each of the routes is associated with a continuous sinusoidal signal of some frequency \({f}_{1}\), \({f}_{2},\dots {f}_{27}\). The values of these frequencies are of no importance. We assume that the phase shifts provided by the cities do not depend on the signal frequency. The problem is solved in two steps. In Step 1, we set up the external phase shifter according to Eqs. (3) and (4). Only the routes coming through all four cities and coming back to Los Angeles will be amplified in the active ring circuit. In Fig. 3C, there are shown phase shifts for all possible routes. Only 6 routes out of 27 satisfy the phase condition (2) and will be amplified. In Step 2, we introduce additional damping for the external electric circuit so only the route with minimum losses can satisfy condition (2). In Fig. 3D, there are shown the results of numerical modeling depicting the shortest route(s) out of six possible from Step 1. Actually, there are always two routes with the shortest distance. In our case, these are Los Angeles–Miami–Washington–Chicago–Los Angeles and Los Angeles–Chicago –Washington–Miami–Los Angeles.

The above-described algorithm can be extended to a larger number of cities. For example, there are shown the schematics of a device for TSP with six cities in Fig. 4. There are two more phase shifters marked as E and F added to the mesh. These shifters provide \(\pi \times \mathit{Log}\left(11\right)\) and \(\pi \times \mathit{Log}\left(13\right)\) phase shifts, respectively. There are more interconnects between the sites of the mesh. Each interconnect is a waveguide that includes an attenuator, a frequency filter, and a power detector. For simplicity, attenuators, filters, and detectors are not shown in Fig. 4. In this example, the traveling salesperson starting from Los Angeles should visit Las Vegas, Chicago, Washington, Miami, San-Francisco, and return to Los Angeles. The map with the cities is shown in Fig. 5A. The table with city-to-city distances can be found in the Supplementary materials. There are more than 3000 possible routes as shown in Fig. 5B. Not all of these routes are coming through all the selected cities. In Step 1, the external phase shifter is tuned to

Schematics of the combinatorial device for TSP with six cities. There are two more phase shifters compared to Fig. 2 marked as E and F added to the mesh. These shifters provide \(\pi \times \mathit{Log}\left(11\right)\) and \(\pi \times \mathit{Log}\left(13\right)\) phase shifts, respectively.

(A) U.S. map with the 20 most fun cities. The traveling salesperson starting from Los Angeles should visit Las Vegas, Chicago, Washington, Miami, San Francisco, and return to Los Angeles. (B) Results of numerical modeling showing the distances for all possible routes. (C) Results of numerical modeling showing phase shifts for all possible routes. (D) Results of numerical modeling depicting the shortest route(s): Los Angeles–Miami–Washington–Chicago–Las Vegas–San Francisco–Los Angeles, and the backward route: Los Angeles–San Francisco–Las Vegas–Chicago–Washington–Miami–Los Angeles.

Only routes coming through all cities (i.e., the routes accumulating the required phase shift) will be amplified. The results of numerical modeling in Fig. 5C show the routes satisfying Eq. (1). In Step 2, additional damping is introduced by the external attenuator. In Fig. 5D, there are shown the shortest routes (i.e., #320 and #3062) that correspond to Los Angeles–Miami–Washington–Chicago–Las Vegas–San Francisco–Los Angeles, and the route with the backward city order: Los Angeles–San Francisco–Las Vegas–Chicago–Washington–Miami–Los Angeles.

It should be noted that in the presented above examples TSP was solved using a general type computer. All possible routes were calculated one by one. Routes with a phase shift satisfying Eq. (1) were selected then. The shortest route out of the routes with the right phase was found by checking all the routes with the right phase. The use of conventional hardware does not provide any advantage over the existing algorithms. To speed up the TSP solution, one needs a device that utilized wave superposition and checks all possible routes in parallel.

In this part, we present experimental data showing TSP solution for four cities. There is a variety of possible approaches to the practical implementation of the device shown in Fig. 2. It may be a superposition of mechanical, acoustic, or electromagnetic waves propagating through all possible routes in the mesh. Our approach is aimed to explore the unique combination of properties inherent in spin waves, where magnetic waveguides can serve as phase shifters and frequency filters at the same time. Spin wave is a collective oscillation of spins in a spin lattice around the direction of magnetization. Spin waves appear in magnetically ordered structures, and a quantum of spin wave is called a “magnon”10. Active ring circuits with spin wave delay lines are widely used as tunable microwave sources11. Radiofrequency spin waves propagate in magnetic waveguides much slower compared to electromagnetic waves in coaxial cables. For instance, the group velocity of magnetostatic spin waves in a single-crystal yttrium iron garnet Y3Fe2(FeO4)3 (YIG) film of thickness 7 µm is about 104 m/s12. It makes it possible to obtain large (e.g., up to 2pi) phase shifts for the propagating signal in millimeter-length waveguides. At the same time, spin wave dispersion strongly depends on waveguide magnetization. Spin waves propagating along the direction of magnetization (so-called backward volume magnetostatic spin waves (BVMSW) and spin waves propagating perpendicular to the direction of magnetization (so-called magnetostatic surface spin waves MSSW) possess different dispersion13. Thus, both the phase shift and the frequency window for spin wave propagation can be controlled by the locally applied magnetic field. It may be just a micro-scale magnet placed on the top of the YIG waveguide. The first proof-of-the-concept experiment on signal re-direction in the two-path combinatorial logic device was accomplished using a YIG-based active ring circuit with BVMSW and MSSW8.

In this work, the mesh is built using commercially available YIG-based frequency filters produced by Micro Lambda Wireless, Inc, model MLFD-40540. The experimental data on the filter transmission and phase delay can be found in the supplementary materials. The schematics of the device are shown in Fig. 6. In Fig. 6A, there is shown the general view of the device similar to the one in Fig. 2. The main difference is in the number of routes connecting the A city on the left and the A city on the right. There are shown nine band-pass filters. The central frequencies of the filters are setup to transmit three selected frequencies: \({f}_{1}=2.441\) GHz, \({f}_{2}=2.514\) GHz, and \({f}_{3}=2.595\) GHz. The filters are assembled to provide three propagation routes: \({f}_{1}\) for A-B-C-D-A, \({f}_{2}\) for A-C-D-B-A, and \({f}_{3}\) for A-D-B-C-A. The device is aimed to find the shortest route depending on the set of attenuators. In Fig. 6B, there are shown the connection schematics of the prototype device. There are six double-channel bandpass frequency filters connected via coaxial cables. The two letters (e.g., AB, CD, etc.) depict the path at which the filter is introduced. For example, AB means that the filter is introduced to the path connecting cities A and B. Each of the filters introduces a phase shift to the propagating signal. This fact is exploited to minimize the number of components in the circuit The phase delay for each city is introduced by the frequency filters. The system was calibrated so the signals propagating through the three routes accumulate the same phase shifts. The amplification in the electric part is provided by three amplifiers (Mini-Circuits, model ZX60-83LN-S+) connected in series. The total amplification is about 15 dB in all experiments. There is external phase shifter (ARRA, model 9418A) which adjusted to provide the phase shift of \(\pi /6\). The phase condition (2) is satisfied for all three routes. Experimental data on signal propagation can be found in the supplementary materials. There are 12 attenuators in the circuit, where the attenuation in dB is proportional to the distance between the cities. The power flow is detected using a unidirectional coupler (KRYTAR, model 1850) which is attached to the 12 selected places as shown in Fig. 6B. These places are marked with numbers 1,2,3 and 4. The marks have different colors (i.e., red, green, and blue) to separate signals propagating on frequencies \({f}_{1}\), \({f}_{2},\) and \({f}_{3}\), respectively. The power detected at port 1 corresponds to the input power. The power measured at ports 2,3, and 4 corresponds to the signal after traveling the first, the second, and the third cities, respectively. Also, the frequency spectra of the auto-oscillation in the active ring circuit can be measured using the Spectrum Analyzer and PNA as shown in Fig. 6B. The spectra can be found in the Supplementary materials.

(A) General view of the prototype device for TSP with four cities. There are 12 single-frequency bandpass filters included in the scheme. The central frequencies of the filters are setup to transmit three selected frequencies: \({f}_{1}=2.441\) GHz, \({f}_{2}=2.514\) GHz, and \({f}_{3}=2.595\) GHz. The filters are assembled to provide three propagation routes: \({f}_{1}\) for A-B-C-D-A, \({f}_{2}\) for A-C-D-B-A, and \({f}_{3}\) for A-D-B-C-A. (B) Connection schematics of the prototype device. The phase delay for each city is introduced by the frequency filters. The system was calibrated so the signals propagating through the three routes accumulate the same phase shifts. There are 12 attenuators in the circuit, where the attenuation in dB is proportional to the distance between the cities. The power flow is detected using a unidirectional coupler (model) which is attached to the 12 selected places marked with numbers 1,2,3, and 4. The marks have different colors (i.e., red, green, and blue) to separate signals propagating on frequencies \({f}_{1}\), \({f}_{2},\) and \({f}_{3}\), respectively.

In the next three examples, we present experimental data demonstrating the shortest route finding depending on the set of attenuators for different paths. It should be noted that not the bandpass frequencies nor connectivity nor the position of the external phase shifter are changed during the experiments.

Experiment 1: In Fig. 7A, there are shown the values of attenuators for different paths. These values are randomly chosen based on the available components. As soon as the magnetic and electric parts are connected, the device starts to search for the resonant path. It takes less than 100 \(\mu s\) for coming to the stable regime of auto-oscillations. In Fig. 7B, there are shown experimental data on the power flow in the circuit. There is about the same input power for all three possible routes. Most of the power flows through the route A-C-D-B-A. There is more than a 30 dBm difference with the other two routes (i.e., A-B-C-D-A and A-D-B-C-A), which are not in resonance with the electric part. The propagation route is illustrated in Fig. 7C. All measurements are done at room temperature.

(A) Node-to-node attenuation. (B) Experimental data on the power flow in the mesh. (C) The shortest route ACDBA is depicted by the power sensors.

Experiment 2: Next, the set of attenuators was changed. In Fig. 8A there are shown the values of attenuators for different paths. In Fig. 8B, there are shown experimental data on the power flow in the circuit. There is about the same input power for all three possible routes. Most of the power flows through the route A-D-B-C-A. As in the previous example, there is more than a 30 dBm difference with the other two routes (i.e., A-B-C-D-A and A-C-D-B-A). The propagation route is illustrated in Fig. 8C.

(A) Node-to-node attenuation for Example 2. (B) Experimental data on the power flow in the mesh. (C) The shortest route ADBCA is depicted by the power sensors.

Experiment 3: In Fig. 9A, there is shown a different set of values of attenuation for different paths. In Fig. 9B, there are shown experimental data on the power flow in the circuit. Most of the power flows through the route A-B-C-D-A. As in the previous example, there is more than a 30 dBm difference with the other two routes (i.e., A-B-C-D-A and A-C-D-B-A). The propagation route is illustrated in Fig. 9C. There is an infinite number of sets for attenuators mimicking the traveling distance between the four cities. In all cases, the device will find the shortest route through all the cities.

(A) Node-to-node attenuation for Example 2. (B) Experimental data on the power flow in the mesh. (C) The shortest route ABCDA is depicted by the power sensors.

There are several observations we would like to make based on the obtained experimental data. The prototype magnonic combinatorial device does show the shortest route of propagation through the selected sites in the mesh made of frequency filters, phase shifters, and attenuators. It is critically important that the change in the signal propagation route demonstrated in the examples is only due to the change in the path attenuation. Thus, the device can be utilized for all possible combinations of path attenuation (distances) between the nodes (cities).

There is a prominent difference in the power flow through the different routes which exceeds 30 dBm at room temperature. The active ring circuit device selectively amplifies only the routes which satisfy resonant conditions (1) and (2). The phase condition (2) allows us to extract the routes with desired accumulated phase change. The amplitude condition (1) makes it possible to select only the shortest route out of many with the same accumulated phase. It takes a special step in numerical modeling for extracting the shortest route by increasing the external attenuation \(R\). The extraction of the shortest route happens naturally in the prototype device due to the non-linear phenomena. This effect is known as mode suppression14,15 which is observed in mechanical, acoustic, and optical resonators. It explains the energy re-distribution of power between the modes, where the mode with minimum attenuation receives the most of the amplification. It is one rare case when the experimental prototype works more efficiently than the theoretical device for numerical modeling.

It should be noted the difference between the general-type device shown in Fig. 2 and the prototype shown in Fig. 4. It is assumed that all routes connecting the A city on the left and the A city on the right are available in the general-type device. As mentioned before, there are “parasitic” routes like A-B-A, A-C-B-A which do not go through all the cities. The “right” routes are selected using the external phase shifter. The device shown in Fig. 2 can be used for finding any route (e.g., A-B-A, A-C-D-A) by adjusting the external phase shifter. In contrast, there are only three routes (i.e., A-B-C-D-A, A-B-D-C-A, and A-C-B-D-A) in the device shown in Fig. 4. It is also possible to include “parasitic” routes in the cost of additional frequency filters. For example, one would need to include two additional frequency filters tuned to the central frequency \({f}_{4}\) to have route A-B-A.

There is a variety of approaches to practical implementation of combinatorial devices. Magnonic approach has certain advantages (e.g., prominent phase shift for RF signal in micro-meter scale waveguides) and disadvantages (e.g., prominent spin wave damping). It may be possible to build optical combinatorial devices with low damping and fast signal propagation if the prominent phase delay can be achieved. The ability to exploit classical wave superposition provides a fundamental advantage over conventional digital computers in functional throughput. Functional throughput is a commonly accepted metric for logic devices evaluation16, which can be defined as follows:

Conventional logic devices based on Complementary Metal-Oxide Semiconductor (CMOS) technology possess deep sub-micrometer characteristic size (e.g., 7 nm channel length) and perform one operation in a very short time (e.g., a fraction of nanosecond)17. However, these Boolean-type devices can accomplish only one operation at a time. In contrast, combinatorial logic devices are efficient in parallel search. This search through multiple routes is equivalent to the number of subsequent operations for the digital computer. The number of possible routes in TSP scales proportional to \(\left(n-1\right)!/2.\) The time of computation scales proportionally to \(n\cdot l/{v}_{g},\) where \(l\) is the length of the waveguide connecting the nodes in the mesh, \({v}_{g}\) is the group velocity of the signal. The area of the mesh scales proportionally to \(\sqrt{n}\cdot {l}^{2}\). The functional throughput of the combinatorial devices for TSP can be estimated as follows:

Taking the length of the waveguide to be 10 mm and the group velocity to be \({10}^{4}\) m/s, the functional throughput is skyrocketing to \({10}^{35}\) Ops/s∙m2 which is above the limits of the existing supercomputers combined.

Surprisingly, there is a lot of similarity in solving different problems such as the Bridges of Konigsberg, TSP, and prime factorization. The use of prime numbers for marking unique mesh nodes (i.e., cities in TSP) looks very efficient and guarantees the uniqueness of the phase accumulated through the different routes. In turn, the same device can be used for prime factorization. The external phase shifter can be set to \(\Psi =2\pi -\pi Log(X)\), where \(X\) is the number to be factorized. The device will find a route at which the accumulated phase matches the external phase. The examples of prime factorization with the combinatorial logic device are presented in the preceding work8. In the future, it may be possible to build a universal combinatorial device capable of solving a variety of NP-hard and NP problems.

The key practical question is related to the number of parts (i.e., waveguides, frequency filters, attenuators, power detectors) for building a device for TSP with a large number of cities. In Table 1, there are shown the estimates for the number of parts for TSP with \(n\) cities. The number of phase shifters for cities scales as \(n+1\). One extra phase shifter is needed for the second A city. The number of waveguides connecting the phase shifters is given by

where the first term on the right accounts for the number of paths in the classical TSP as shown in Fig. 2. The second term on the right accounts for the additional \(\left(n-1\right)\) waveguides for the second city A. There is the same number of attenuators and power detectors required for TSP with \(n\) cities. A more complicated is situation with frequency filters. There are 12 single-frequency bandpass filters (4 filters for 3 routes) shown in Fig. 6A. In the prototype, we used separate cables and frequency filters to make two propagation paths between some cities (e.g., BC and DC). It would take an enormous amount \(\left(n-1\right)!\) of single-frequency bandpass filters for TSP with \(n\) cities following this approach. In general, an \(i-th\) route in the combinatorial device should be associated with some frequency \({f}_{i}\). It leads to the grand challenge of the presented approach as the number of possible routes increases factorial with the number of cities. The number of distinct frequencies can be quite large (e.g., 1 M frequencies in the frequency range from 0.5 to 10 GHz with the inter-frequency separation of 0.5 MHz). However, it is sufficient for solving TSP with just 6–7 cities. In part, this problem can be resolved by utilizing the same frequency for not-crossing routes. The problem can be resolved completely by utilizing combinatorial filters transmitting signals comprising waves with a certain combination of frequencies (e.g., \({\{f}_{1}\), \({f}_{2},\) \({f}_{5}\), \({f}_{11}\}\) or \({\{f}_{2}\), \({f}_{4},\) \({f}_{7}\), \({f}_{19}\},\) etc.). In this scenario, the number of filters is the same as the number of waveguides given by Eq. (8), where each filter has a unique combination of the bandpass frequencies. In all cases, there is only one external broadband amplifier, one external tunable phase shifter, and one external tunable attenuator.

It should be noted that every new problem requires circuit adjustment or reconfiguration. For instance, the circuit for four cities presented in this work can be used for any other TSP with four cities. One needs to adjust the attenuation according to the distances between the cities. It can be done using voltage-tunable attenuators. The increase in the number of cities requires an increase in the number of phase shifters in the circuit. However, TSP circuits can be used for a smaller number of cities without removing/adding new components. For example, TSP with eight cities can be used for solving problems for eight, seven, six, five, and four cities.

Another practical challenge is associated with the accuracy of the parts with respect to the number of cities. The difference in the distances between the cities may significantly decrease for TSPs with a large number of cities. There are physical limits to the accuracy of attenuator control. Also, the increase of possible propagation routes inevitably decreases the difference in the accumulated phase for different routes. In turn, it will lead to the problem with the shortest route finding for a large number of cities. The increase in the precision of measurements/calculations is a common problem for TSP with a large number of cities that may be addressed with heuristic algorithms18. Less accuracy is required for the power detectors. A prominent difference in the power flow (e.g., a 20 dB difference between the active and passive routes) can be achieved regardless of the number of cities. There are certain pros and cons of using magnonic circuits for TSP. On the one hand, spin waves provide prominent phase shifts on millimeter-length waveguides. On the other hand, spin wave dispersion significantly complicates circuit engineering. Besides, spin waves possess much stronger interaction compared to optical waves. For instance, spin waves propagating in the orthogonal directions through the junction may completely reflect each other19. It constitutes an additional problem for spin wave interconnects. This and many other questions deserve special consideration.

We described an approach to TSP solution using combinatorial devices. The principle of operation is based on the classical wave superposition, where each wave corresponds to a traveling salesman. The waves propagate through a mesh of waveguides, where phase shifters represent the cities in TSP and the distance between the cities is encoded in the signal attenuation. Only waves coming through the selected cities and accumulating the specific phase shift are amplified. The most amplified is the wave traveling through the route with minimum attenuation. TSP solution is illustrated by numerical modeling and experimentally demonstrated. The first prototype is a multi-path magnonic active ring circuit comprising magnetic phase shifters, frequency filters, and attenuators. The signal propagation route is detected via the power detector. We presented thee examples for three different sets of attenuators/city-to-city distances. The device literally finds the shortest propagating route through the cities. The operation is robust as the power difference between the active and passive routes exceeds 30 dBm. All experiments are accomplished at room temperature. This work is a step toward combinatorial logic devices for special task data processing. Potentially, combinatorial devices may provide a fundamental advantage in functional throughput compared to conventional digital devices. The ability to use classical superposition of waves is the key advantage and the most appealing property of the presented approach.

All data generated or analyzed during this study are included in this published article.

Biggs, N., Lloyd, E. K. & Wilson, R. J. Graph theory, 1736–1936. Isis 70, 164–165. https://doi.org/10.1086/352170 (1979).

Article MATH Google Scholar

Ungureanu, V. Traveling salesman problem with transportation. Comput. Sci. J. Mold. 14, 202–206 (2006).

MATH Google Scholar

Fuentes, G. E. A., Gress, E. S. H., Mora, J. & Marin, J. M. Solution of the job-shop scheduling problem through the traveling salesman problem. Rev. Iberoam. Autom. Inform. Ind. 13, 430–437. https://doi.org/10.1016/j.riai.2016.07.003 (2016).

Article Google Scholar

Gusfield, D. & Gusfield, D. Traveling Salesman Problems in Genomics (Cambridge Univ Press, 2019).

Book MATH Google Scholar

Aarts, E. H. L. & Korst, J. H. M. Boltzmann machines for traveling salesman problems. Eur. J. Oper. Res. 39, 79–95. https://doi.org/10.1016/0377-2217(89)90355-x (1989).

Article MATH Google Scholar

Collings, N., Sumi, R., Weible, K. J., Acklin, B. & Xue, W. InInternational Topical Meeting on Optical Computing (Oc 92). 637–641 (Spie-Int Soc Optical Engineering, 1993).

Saud, S., Kodaz, H. & Babaoglu, I. In 9th International Conference on Advances in Information Technology (IAIT). 17–32 (Knowledge E, 2018).

Khitun, A. & Balinskiy, M. Combinatorial logic devices based on a multi-path active ring circuit. Sci. Rep. https://doi.org/10.1038/s41598-022-13614-2 (2022).

Article PubMed PubMed Central Google Scholar

Tiberkevich, V. S., Khymyn, R. S., Tang, H. X. & Slavin, A. N. Sensitivity to external signals and synchronization properties of a non-isochronous auto-oscillator with delayed feedback. Sci. Rep. https://doi.org/10.1038/srep03873 (2014).

Article PubMed PubMed Central Google Scholar

Kittel, C. Introduction to Solid State Physics 8th edn. (Wiley, 2005).

MATH Google Scholar

Chumak, A. V., Serga, A. A. & Hillebrands, B. Magnonic crystals for data processing. J. Phys. D-Appl. Phys. 50, 1–20. https://doi.org/10.1088/1361-6463/aa6a65 (2017).

Article CAS Google Scholar

Balinskiy, M. et al. Spin wave interference in YIG cross junction. Aip Adv. https://doi.org/10.1063/1.4974526 (2017).

Article Google Scholar

Gurevich, A. G. & Melkov, G. A. Magnetization Oscillations and Waves 147–176 (CRC Press, 1996).

Google Scholar

Okusaga, O. et al. In 2010 IEEE International Frequency Control Symposium. 539–543 (IEEE, 2010).

Carroll, J. M. & Chang, K. Microstrip mode suppression ring-resonator. Electron. Lett. 30, 1861–1862. https://doi.org/10.1049/el:19941291 (1994).

Article ADS Google Scholar

Nikonov, D. E. & Young, I. A. Uniform methodology for benchmarking beyond-CMOS logic devices. In 2012 IEEE International Electron Devices Meeting (IEDM 2012), vol. 25, https://doi.org/10.1109/iedm.2012.6479102 (2012).

Hoefflinger, B. In Chips 2020, Vol. 2: New Vistas in Nanoelectronics Frontiers Collection (ed, Hoefflinger, B.) 143–148 (Springer, 2016).

Syambas, N. R., Salsabila, S., Suranegara, G. M. & IEEE. In 11th International Conference on Telecommunication Systems Services and Applications (TSSA). (IEEE, 2017).

Balynskiy, M. et al. Reversible magnetic logic gates based on spin wave interference. J. Appl. Phys. https://doi.org/10.1063/1.5011772 (2018).

Article Google Scholar

Download references

This work of M. Balinskiy and A. Khitun was supported in part by the INTEL CORPORATION, under Award #008635, Project director Dr. D. E. Nikonov, and by the National Science Foundation (NSF) under Award # 2006290, Program Officer Dr. S. Basu. The authors would like to thank Dr. D. E. Nikonov for the valuable discussions.

Department of Electrical and Computer Engineering, University of California-Riverside, Riverside, CA, 92521, USA

Mykhaylo Balinskyy & Aleksandr Khitun

You can also search for this author in PubMed Google Scholar

You can also search for this author in PubMed Google Scholar

A.K. conceived the idea of combinatorial magnonic devices for TSP and wrote the manuscript, M.B. built the prototype and carried out the experiments. All authors discussed the data and contributed to the manuscript preparation.

Correspondence to Aleksandr Khitun.

The authors declare no competing interests.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Reprints and Permissions

Balinskyy, M., Khitun, A. Traveling salesman problem solution using magnonic combinatorial device. Sci Rep 13, 11708 (2023). https://doi.org/10.1038/s41598-023-38839-7

Download citation

Received: 17 March 2023

Accepted: 16 July 2023

Published: 20 July 2023

DOI: https://doi.org/10.1038/s41598-023-38839-7

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

By submitting a comment you agree to abide by our Terms and Community Guidelines. If you find something abusive or that does not comply with our terms or guidelines please flag it as inappropriate.