International Defense Security & Technology Your trusted Source for News, Research and Analysis
Quantum walks are the quantum version of classical random walks, which are a mathematical means for describing a natural random walk, e.g., simply wandering around randomly.
In a “classical random walk”, you could imagine someone starting at the centre of a city, and making a random decision at each intersection. In this case, the walker’s position is described by a probability distribution over all the possible positions (kind of like the wear on a stone step is a probability distribution of where feet land).
In the quantum world, superposition (the property of quanta that they may exist in a superposition of multiple states at once until the waveform is collapsed) is added to the mix. In other words, the walker may be superposed over all positions until measured.
Chinese researchers have demonstrated a two-dimensional continuous-time quantum walk by using the external geometry of photonic waveguide arrays, rather than the inner degree of freedoms of photons. Using femtosecond laser direct writing, they constructed a large-scale three-dimensional structure that forms a two-dimensional lattice with up to 49 × 49 nodes on a photonic chip.
Quantum Walks
Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation.
In particular, they are central to quantum algorithms created to tackle database search, graph isomorphism, network analysis and navigation and quantum simulation as well as modelling biological processes. Meanwhile, physical properties of quantum walks have been demonstrated in a variety of systems, such as nuclear magnetic resonance, bulk and fibre optics, trapped ions, trapped neutral atoms and photonics. Almost all physical implementations of quantum walk so far followed an analogue approach as for quantum simulation, whereby the apparatus is dedicated to implement specific instances of Hamiltonians without translation onto quantum logic. However, there is no existing method to implement analogue quantum simulations with error correction or fault tolerance, and they do not scale efficiently in resources when simulating broad classes of large graphs.
To describe such walks, mathematicians and computer scientists use probability distribution grids that show a current position and possible next steps. Quantum walks are used to build models that depict randomly grown, sophisticated and complex networks such as the human neural network. They can also be used to create networks for actual use in applications, and might one day be used in quantum-based robots.
Quantum walks are motivated by the widespread use of classical random walks in the design of randomized algorithms, and are part of several quantum algorithms. For some oracular problems, quantum walks provide an exponential speedup over any classical algorithm. Quantum walks also give polynomial speedups over classical algorithms for many practical problems, such as the element distinctness problem, the triangle finding problem, and evaluating NAND trees. The well-known Grover search algorithm can also be viewed as a quantum walk algorithm.
Quantum walks, in virtue of the coherent superposition and quantum interference, have exponential superiority over their classical counterpart in applications of quantum searching and quantum simulation. The quantum-enhanced power is highly related to the state space of quantum walks, which can be expanded by enlarging the photon number and/or the dimensions of the evolution network, but the former is considerably challenging due to probabilistic generation of single photons and multiplicative loss.
A chip that allows for two-dimensional quantum walks
A team of researchers from Shanghai Jiao Tong University and the University of Science and Technology of China has developed a chip that allows for two-dimensional quantum walks of single photons on a physical device.
According to the researchers, most quantum walk demonstrations so far have been single dimensional, which is useful to show that the states can be created, but not for simulation problems. For example, the paper states, “In the spatial search algorithm, a quantum walk outperforms its classical counterparts only when the dimension is higher than one”.
As the researchers note, a quantum computer should provide exponential advantages over classical systems due to their nature. To that end, scientists have been working to implement quantum walks in a physical machine as part of developing a truly useful quantum computer. In this new effort, the researchers report that they have developed a chip that carries out quantum walks on a two-dimensional 49×49 grid—the largest created so far by any team.
The “quantum walk” doesn’t deliver a general-purpose quantum computer. Instead it delivers a quantum simulator which the scientists told China’s state-controlled Xinhua news agency can “solve practical problems directly without error correction, and potentially be able to beat the computational power of classical computers in the near future
They claim the scale of their 49 x 49 array should provide a measurable speed-up over classical simulators, for at least that class of problems quantum walks can simulate – for example, predicting the behaviour of randomly-grown networks such as in “simulation of graphene, photosynthesis, or neural network systems”.
The three-dimensional chip, the team reports, was created using a technique called femtosecond writing. It uses the external geometry of photonic waveguide arrays as a means for carrying out the quantum walks using a single photon. They note also that they tested the chip by observing patterns and variance profiles and comparing them to simulation studies. They suggest further that in addition to making progress toward a truly useful quantum computer, the chip could also be used to boost the performance of analog quantum computing or quantum simulators.
If researchers can create quantum computers with very large, or even unlimited size grids, it might be possible to create and use networks as complex as the human nervous system.
References and Resources also include:
https://phys.org/news/2018-05-chip-two-dimensional-quantum.html
