Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the sy...Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the symmetry of a graph, especially that of a tree. Firstly, we prove in mathematics that the symmetry of a graph is highly related to quantum walk. Secondly, we propose an algorithm based on the continuous-time quantum walk to compute the symmetry of a tree. Our algorithm has better time complexity O（N3） than the current best algorithm. Finally, through testing three types of 10024 trees, we find that the symmetry of a tree can be found with an extremely high efficiency with the help of the continuous-time quantum walk.展开更多
Programmable two-particle quantum walks are crucial for advancing quantum simulation,computation,and information processing.Although disorder is traditionally associated with information loss,it can also facilitate em...Programmable two-particle quantum walks are crucial for advancing quantum simulation,computation,and information processing.Although disorder is traditionally associated with information loss,it can also facilitate emergent phenomena such as enhanced energy transport.Here,we experimentally realize a 12-step discrete-time quantum walk in programmable integrated photonic circuits,introducing tunable static and dynamic disorder to explore quantum transport dynamics.In periodic lattices,disorder induces light localization and drives a transition from quantum ballistic to classical diffusive behavior.In particular,quantum walks of correlated photons exhibit a disorder-induced bunching effect,accompanied by enhanced nonclassical correlations.Our platform provides a scalable framework for investigating multiparticle quantum dynamics in engineered environments,promoting the development of quantum optics toward large-scale applications.展开更多
In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability o...In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.展开更多
The continuous-time quantum walk(CTQW) is the quantum analogue of the continuous-time classical walk and is widely used in universal quantum computations. Here, taking the advantages of the waveguide arrays, we implem...The continuous-time quantum walk(CTQW) is the quantum analogue of the continuous-time classical walk and is widely used in universal quantum computations. Here, taking the advantages of the waveguide arrays, we implement large-scale CTQWs on chips. We couple the single-photon source into the middle port of the waveguide arrays and measure the emergent photon number distributions by utilizing the fiber coupling platform. Subsequently, we simulate the photon number distributions of the waveguide arrays by considering the boundary conditions. The boundary conditions are quite necessary in solving the problems of quantum mazes.展开更多
The no-cloning theorem has sparked considerable interest in achieving high-fidelity approximate quantum cloning.Most of the previous studies mainly focused on the cloning of single particle states,and cloning schemes ...The no-cloning theorem has sparked considerable interest in achieving high-fidelity approximate quantum cloning.Most of the previous studies mainly focused on the cloning of single particle states,and cloning schemes used there are incapable of cloning quantum entangled states in multipartite systems.Few schemes were proposed for cloning multiparticle states,which consume more entanglement resources with loss of qubits,and the fidelity of the cloned state is relatively low.In this paper,cloning schemes for bipartite and tripartite entangled states based on photonic quantum walk and entanglement swapping are proposed.The results show that according to the proposed schemes,two high-fidelity(up to 0.75)cloned states can be obtained with less quantum resource consumption.Because of the simple cloning steps,few quantum resources and high fidelity,these schemes are both efficient and feasible.Moreover,this cloning machine eliminates the need for tracing out cloning machine,thereby minimizing resource waste.展开更多
Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we de...Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms.We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities.These probabilities are fundamentally determined by specific initial state properties:the coherence fraction governs the first algorithm’s performance,while entanglement and coherence dominate the outcomes of the second and third algorithms,respectively.We show that increased coherence fraction enhances success probability,but greater entanglement and coherence reduce it in the latter two cases.These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design.Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.展开更多
Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science.The mixing property is necessary for Markov chains to approach stationary distribution...Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science.The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks.Quantum walks show promise for faster mixing times than classical methods but lack universal proof,especially in finite group settings.Here,we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D_(2n)for odd n,generated by the smallest inverse closed symmetric subset.We present a significant finding that,in contrast to the classical mixing time on these Cayley graphs,which typically takes at least orderΩ(n^(2)log(1/2∈)),the continuous-time quantum walk mixing time on D_(2n)is of order O(n(log n)^(5)log(1/∈)),achieving a quadratic improvement over the classical case.Our paper advances the general understanding of quantum walk mixing on Cayley graphs,highlighting the improved mixing time achieved by continuous-time quantum walks on D_(2n).This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.展开更多
Topological phases and their associated multiple edge states are studied by constructing a one-dimensional non-unitary multi-period quantum walk with parity-time symmetry.It is shown that large topological numbers can...Topological phases and their associated multiple edge states are studied by constructing a one-dimensional non-unitary multi-period quantum walk with parity-time symmetry.It is shown that large topological numbers can be obtained when choosing an appropriate time frame.The maximum value of the winding number can reach the number of periods in the one-step evolution operator.The validity of the bulk-edge correspondence is confirmed,while for an odd-period quantum walk and an even-period quantum walk,they have different configurations of the 0-energy edge state andπ-energy edge state.On the boundary,two kinds of edge states always coexist in equal amount for the odd-period quantum walk,however three cases including equal amount,unequal amount or even only one type may occur for the even-period quantum walk.展开更多
This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the se...This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q. For a given q, we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.展开更多
This paper investigates the effects of decoherence generated by broken-link-type noise in the hypercube on an optimized quantum random-walk search algorithm. When the hypercube occurs with random broken links, the opt...This paper investigates the effects of decoherence generated by broken-link-type noise in the hypercube on an optimized quantum random-walk search algorithm. When the hypercube occurs with random broken links, the optimized quantum random-walk search algorithm with decoherence is depicted through defining the shift operator which includes the possibility of broken links. For a given database size, we obtain the maximum success rate of the algorithm and the required number of iterations through numerical simulations and analysis when the algorithm is in the presence of decoherence. Then the computational complexity of the algorithm with decoherence is obtained. The results show that the ultimate effect of broken-link-type decoherence on the optimized quantum random-walk search algorithm is negative.展开更多
Shenvi et al.have proposed a quantum algorithm based on quantum walking called Shenvi-Kempe-Whaley(SKW)algorithm,but this search algorithm can only search one target state and use a specific search target state vector...Shenvi et al.have proposed a quantum algorithm based on quantum walking called Shenvi-Kempe-Whaley(SKW)algorithm,but this search algorithm can only search one target state and use a specific search target state vector.Therefore,when there are more than two target nodes in the search space,the algorithm has certain limitations.Even though a multiobjective SKW search algorithm was proposed later,when the number of target nodes is more than two,the SKW search algorithm cannot be mapped to the same quotient graph.In addition,the calculation of the optimal target state depends on the number of target states m.In previous studies,quantum computing and testing algorithms were used to solve this problem.But these solutions require more Oracle calls and cannot get a high accuracy rate.Therefore,to solve the above problems,we improve the multi-target quantum walk search algorithm,and construct a controllable quantum walk search algorithm under the condition of unknown number of target states.By dividing the Hilbert space into multiple subspaces,the accuracy of the search algorithm is improved from p_(c)=(1/2)-O(1/n)to p_(c)=1-O(1/n).And by adding detection gate phase,the algorithm can stop when the amplitude of the target state becomes the maximum for the first time,and the algorithm can always maintain the optimal number of iterations,so as to reduce the number of unnecessary iterations in the algorithm process and make the number of iterations reach t_(f)=(π/2)(?).展开更多
We propose an efficient quantum private comparison protocol firstly based on one direction quantum walks.With the help of one direction quantum walk,we develop a novel method that allows the semi-honest third party to...We propose an efficient quantum private comparison protocol firstly based on one direction quantum walks.With the help of one direction quantum walk,we develop a novel method that allows the semi-honest third party to set a flag to judge the comparing result,which improves the qubit efficiency and the maximum quantity of the participants’secret messages.Besides,our protocol can judge the size of the secret messages,not only equality.Furthermore,the quantum walks particle is disentangled in the initial state.It only requires a quantum walks operator to move,making our proposed protocol easy to implement and reducing the quantum resources.Through security analysis,we prove that our protocol can withstand well-known attacks and brute-force attacks.Analyses also reveal that our protocol is correct and practical.展开更多
As an important branch of machine learning,clustering analysis is widely used in some fields,e.g.,image pattern recognition,social network analysis,information security,and so on.In this paper,we consider the designin...As an important branch of machine learning,clustering analysis is widely used in some fields,e.g.,image pattern recognition,social network analysis,information security,and so on.In this paper,we consider the designing of clustering algorithm in quantum scenario,and propose a quantum hierarchical agglomerative clustering algorithm,which is based on one dimension discrete quantum walk with single-point phase defects.In the proposed algorithm,two nonclassical characters of this kind of quantum walk,localization and ballistic effects,are exploited.At first,each data point is viewed as a particle and performed this kind of quantum walk with a parameter,which is determined by its neighbors.After that,the particles are measured in a calculation basis.In terms of the measurement result,every attribute value of the corresponding data point is modified appropriately.In this way,each data point interacts with its neighbors and moves toward a certain center point.At last,this process is repeated several times until similar data points cluster together and form distinct classes.Simulation experiments on the synthetic and real world data demonstrate the effectiveness of the presented algorithm.Compared with some classical algorithms,the proposed algorithm achieves better clustering results.Moreover,combining quantum cluster assignment method,the presented algorithm can speed up the calculating velocity.展开更多
The present paper is focused on non-uniform quantum coins for the quantum random walk search algorithm. This is an alternative to the modification of the shift operator, which divides the search space into two parts. ...The present paper is focused on non-uniform quantum coins for the quantum random walk search algorithm. This is an alternative to the modification of the shift operator, which divides the search space into two parts. This method changes the quantum coins, while the shift operator remains unchanged and sustains the hypercube topology. The results discussed in this paper are obtained by both theoretical calculations and numerical simulations.展开更多
We study the entanglement between the internal(coin)and the external(position)degrees of freedom in the dynamic and the static deterministic aperiodic quantum walks(QWs).For the dynamic(static)aperiodic QWs,the coin d...We study the entanglement between the internal(coin)and the external(position)degrees of freedom in the dynamic and the static deterministic aperiodic quantum walks(QWs).For the dynamic(static)aperiodic QWs,the coin depends on the time(position)and takes two coins C(α)and C(β)arranged in the two classes of generalized Fibonacci(GF)and the Thue–Morse(TM)sequences.We found that for the dynamic QWs,the entanglement of three kinds of the aperiodic QWs are close to the maximal value,which are all much larger than that of the homogeneous QWs.Further,the first class of GF(1st GF)QWs can achieve the maximum entangled state,which is similar to that of the dynamic disordered QWs.And the entanglement of 1st GF QWs is greater than that of the TM QWs,being followed closely by the entanglement of the second class of GF(2nd GF)QWs.For the static QWs,the entanglement of three kinds of the aperiodic QWs are also close to the maximal value and 1st GF QWs can achieve the maximum entangled state.The entanglement of the TM QWs is between1st GF QWs and 2nd GF QWs.However,the entanglement of the static disordered QWs is less than that of three kinds of the aperiodic QWs.This is different from those of the dynamic QWs.From these results,we can conclude that the dynamic and static 1st GF QWs can also be considered as maximal entanglement generators.展开更多
In the optical quantum random walk system,phase nuctuation and Deam splitter uuctuation are two unavoldable decoherence factors.These two factors degrade the performance of quantum random walk by destroying coherence,...In the optical quantum random walk system,phase nuctuation and Deam splitter uuctuation are two unavoldable decoherence factors.These two factors degrade the performance of quantum random walk by destroying coherence,and even degrade it into a classical one.We propose a scheme for the simulation of quantum random walk using phase shifters,tunable beam splitters,and photodetectors.This proposed scheme enables us to analyze the effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk.Furthermore,it is helpful to guide the control of phase fluctuation and beam snlitter fluctuation in the exneriment.展开更多
This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this ...This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established, and the relationship between the success rate of the algorithm, the database size, the number of iterations, and the phase error is determined. For a given database size, we obtain both the maximum success rate of the algorithm and the required number of iterations when phase errors are present in the algorithm. Analyses and numerical simulations show that the optimized quantum random-walk search algorithm is more robust against phase errors than Grover＇s algorithm.展开更多
We present a numerical study of a model of quantum walk in a periodic potential on a line. We take the simple view that different potentials have different affects on the way in which the coin state of the walker is c...We present a numerical study of a model of quantum walk in a periodic potential on a line. We take the simple view that different potentials have different affects on the way in which the coin state of the walker is changed. For simplicity and definiteness, we assume that the walker＇s coin state is unaffected at sites without the potential, and rotated in an unbiased way according to the Hadamard matrix at sites with the potential. This is the simplest and most natural model of a quantum walk in a periodic potential with two coins. Six generic cases of such quantum walks are studied numerically. It is found that, of the six cases, four cases display significant localization effect where the walker is confined in the neighborhood of the origin for a sufficiently long time. Associated with such a localization effect is the recurrence of the probability of the walker returning to the neighborhood of the origin.展开更多
Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of...Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of quantum walks under different decoherence situations. In this article, we study a non-Markovian decoherent quantum walk on a line. In a short time regime, the behavior of the walk deviates from both ideal quantum walks and classical random walks. The position variance as a measure of the quantum walk collapses and revives for a short time, and tends to have a linear relation with time. That is, the walker’s behavior shows a diffusive spread over a long time limit, which is caused by non-Markovian dephasing affecting the quantum correlations between the quantum walker and his coin. We also study both quantum discord and measurement-induced disturbance as measures of the quantum correlations, and observe both collapse and revival in the short time regime, and the tendency to be zero in the long time limit. Therefore, quantum walks with non-Markovian decoherence tend to have diffusive spreading behavior over long time limits, while in the short time regime they oscillate between ballistic and diffusive spreading behavior, and the quantum correlation collapses and revives due to the memory effect.展开更多
This article aims to provide a review on quantum walks. Starting form a basic idea of discrete-time quantum walks, we will review the impact of disorder and decoherence on the properties of quantum walks. The evolutio...This article aims to provide a review on quantum walks. Starting form a basic idea of discrete-time quantum walks, we will review the impact of disorder and decoherence on the properties of quantum walks. The evolution of the standard quantum walks is deterministic and disorder introduces randomness to the whole system and change interference pattern leading to the localization effect. Whereas, decoherence plays the role of transmitting quantum walks to classical random walks.展开更多
基金Project supported by the National Natural Science Foundation of China (Grant No. 61003082)
文摘Quantum walk, the quantum counterpart of random walk, is an important model and widely studied to develop new quantum algorithms. This paper studies the relationship between the continuous-time quantum walk and the symmetry of a graph, especially that of a tree. Firstly, we prove in mathematics that the symmetry of a graph is highly related to quantum walk. Secondly, we propose an algorithm based on the continuous-time quantum walk to compute the symmetry of a tree. Our algorithm has better time complexity O（N3） than the current best algorithm. Finally, through testing three types of 10024 trees, we find that the symmetry of a tree can be found with an extremely high efficiency with the help of the continuous-time quantum walk.
基金supported by the National Natural Science Foundation of China(Grant Nos.T2325022,U23A2074,12204462,62275240,62435009,12474494,and 12204468)the Chinese Academy of Sciences(CAS)Project for Young Scientists in Basic Research(Grant No.253 YSBR-049)+3 种基金the Key Research and Development Program of Anhui Province(Grant No.2022b1302007)the China Postdoctoral Science Foundation(Grant No.2024M753083)the National Postdoctoral Program for Innovative Talents(Grant No.BX20240353)the Fundamental Research Funds for the Central Universities(Grant Nos.WK2030000107,WK2030000108,and WK2030000081)。
文摘Programmable two-particle quantum walks are crucial for advancing quantum simulation,computation,and information processing.Although disorder is traditionally associated with information loss,it can also facilitate emergent phenomena such as enhanced energy transport.Here,we experimentally realize a 12-step discrete-time quantum walk in programmable integrated photonic circuits,introducing tunable static and dynamic disorder to explore quantum transport dynamics.In periodic lattices,disorder induces light localization and drives a transition from quantum ballistic to classical diffusive behavior.In particular,quantum walks of correlated photons exhibit a disorder-induced bunching effect,accompanied by enhanced nonclassical correlations.Our platform provides a scalable framework for investigating multiparticle quantum dynamics in engineered environments,promoting the development of quantum optics toward large-scale applications.
文摘In this paper we define direct product of graphs and give a recipe for obtaining probability of observing particle on vertices in the continuous-time classical and quantum random walk. In the recipe, the probability of observing particle on direct product of graph is obtained by multiplication of probability on the corresponding to sub-graphs, where this method is useful to determining probability of walk on compficated graphs. Using this method, we calculate the probability of Continuous-time classical and quantum random walks on many of finite direct product Cayley graphs （complete cycle, complete Kn, charter and n-cube）. Also, we inquire that the classical state the stationary uniform distribution is reached as t→∞ but for quantum state is not always satisfied.
基金supported by the National Natural Science Foundation of China(Nos.61627820,11674306,61590932,and 61377048)
文摘The continuous-time quantum walk(CTQW) is the quantum analogue of the continuous-time classical walk and is widely used in universal quantum computations. Here, taking the advantages of the waveguide arrays, we implement large-scale CTQWs on chips. We couple the single-photon source into the middle port of the waveguide arrays and measure the emergent photon number distributions by utilizing the fiber coupling platform. Subsequently, we simulate the photon number distributions of the waveguide arrays by considering the boundary conditions. The boundary conditions are quite necessary in solving the problems of quantum mazes.
文摘The no-cloning theorem has sparked considerable interest in achieving high-fidelity approximate quantum cloning.Most of the previous studies mainly focused on the cloning of single particle states,and cloning schemes used there are incapable of cloning quantum entangled states in multipartite systems.Few schemes were proposed for cloning multiparticle states,which consume more entanglement resources with loss of qubits,and the fidelity of the cloned state is relatively low.In this paper,cloning schemes for bipartite and tripartite entangled states based on photonic quantum walk and entanglement swapping are proposed.The results show that according to the proposed schemes,two high-fidelity(up to 0.75)cloned states can be obtained with less quantum resource consumption.Because of the simple cloning steps,few quantum resources and high fidelity,these schemes are both efficient and feasible.Moreover,this cloning machine eliminates the need for tracing out cloning machine,thereby minimizing resource waste.
基金supported by the Fundamental Research Funds for the Central Universities,the National Natural Science Foundation of China(Grant Nos.12371132,12075159,12171044,12071179,and 12405006)the specific research fund of the Innovation Platform for Academicians of Hainan Province.
文摘Quantum algorithms have demonstrated provable speedups over classical counterparts,yet establishing a comprehensive theoretical framework to understand the quantum advantage remains a core challenge.In this work,we decode the quantum search advantage by investigating the critical role of quantum state properties in random-walk-based algorithms.We propose three distinct variants of quantum random-walk search algorithms and derive exact analytical expressions for their success probabilities.These probabilities are fundamentally determined by specific initial state properties:the coherence fraction governs the first algorithm’s performance,while entanglement and coherence dominate the outcomes of the second and third algorithms,respectively.We show that increased coherence fraction enhances success probability,but greater entanglement and coherence reduce it in the latter two cases.These findings reveal fundamental insights into harnessing quantum properties for advantage and guide algorithm design.Our searches achieve Grover-like speedups and show significant potential for quantum-enhanced machine learning.
基金supported by the Key-Area Research and Development Program of Guang-Dong Province(Grant No.2018B030326001)the National Natural Science Foundation of China(U1801661)Shenzhen Science and Technology Program(KQTD20200820113010023)。
文摘Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science.The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks.Quantum walks show promise for faster mixing times than classical methods but lack universal proof,especially in finite group settings.Here,we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group D_(2n)for odd n,generated by the smallest inverse closed symmetric subset.We present a significant finding that,in contrast to the classical mixing time on these Cayley graphs,which typically takes at least orderΩ(n^(2)log(1/2∈)),the continuous-time quantum walk mixing time on D_(2n)is of order O(n(log n)^(5)log(1/∈)),achieving a quadratic improvement over the classical case.Our paper advances the general understanding of quantum walk mixing on Cayley graphs,highlighting the improved mixing time achieved by continuous-time quantum walks on D_(2n).This work has potential applications in algorithms for a class of sampling problems based on non-abelian groups.
基金supported by the National Natural Science Foundation of China(Grant No.12004231).
文摘Topological phases and their associated multiple edge states are studied by constructing a one-dimensional non-unitary multi-period quantum walk with parity-time symmetry.It is shown that large topological numbers can be obtained when choosing an appropriate time frame.The maximum value of the winding number can reach the number of periods in the one-step evolution operator.The validity of the bulk-edge correspondence is confirmed,while for an odd-period quantum walk and an even-period quantum walk,they have different configurations of the 0-energy edge state andπ-energy edge state.On the boundary,two kinds of edge states always coexist in equal amount for the odd-period quantum walk,however three cases including equal amount,unequal amount or even only one type may occur for the even-period quantum walk.
基金supported by the National Basic Research Program of China(Grant No.2013CB338002)
文摘This study investigates the multi-solution search of the optimized quantum random-walk search algorithm on the hypercube. Through generalizing the abstract search algorithm which is a general tool for analyzing the search on the graph to the multi-solution case, it can be applied to analyze the multi-solution case of quantum random-walk search on the graph directly. Thus, the computational complexity of the optimized quantum random-walk search algorithm for the multi-solution search is obtained. Through numerical simulations and analysis, we obtain a critical value of the proportion of solutions q. For a given q, we derive the relationship between the success rate of the algorithm and the number of iterations when q is no longer than the critical value.
基金supported by the National Basic Research Program of China(Grant No.2013CB338002)
文摘This paper investigates the effects of decoherence generated by broken-link-type noise in the hypercube on an optimized quantum random-walk search algorithm. When the hypercube occurs with random broken links, the optimized quantum random-walk search algorithm with decoherence is depicted through defining the shift operator which includes the possibility of broken links. For a given database size, we obtain the maximum success rate of the algorithm and the required number of iterations through numerical simulations and analysis when the algorithm is in the presence of decoherence. Then the computational complexity of the algorithm with decoherence is obtained. The results show that the ultimate effect of broken-link-type decoherence on the optimized quantum random-walk search algorithm is negative.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.11975132 and 61772295)the Natural Science Foundation of Shandong Province,China(Grant No.ZR2019YQ01)the Project of Shandong Provincial Higher Educational Science and Technology Program,China(Grant No.J18KZ012)。
文摘Shenvi et al.have proposed a quantum algorithm based on quantum walking called Shenvi-Kempe-Whaley(SKW)algorithm,but this search algorithm can only search one target state and use a specific search target state vector.Therefore,when there are more than two target nodes in the search space,the algorithm has certain limitations.Even though a multiobjective SKW search algorithm was proposed later,when the number of target nodes is more than two,the SKW search algorithm cannot be mapped to the same quotient graph.In addition,the calculation of the optimal target state depends on the number of target states m.In previous studies,quantum computing and testing algorithms were used to solve this problem.But these solutions require more Oracle calls and cannot get a high accuracy rate.Therefore,to solve the above problems,we improve the multi-target quantum walk search algorithm,and construct a controllable quantum walk search algorithm under the condition of unknown number of target states.By dividing the Hilbert space into multiple subspaces,the accuracy of the search algorithm is improved from p_(c)=(1/2)-O(1/n)to p_(c)=1-O(1/n).And by adding detection gate phase,the algorithm can stop when the amplitude of the target state becomes the maximum for the first time,and the algorithm can always maintain the optimal number of iterations,so as to reduce the number of unnecessary iterations in the algorithm process and make the number of iterations reach t_(f)=(π/2)(?).
基金Project supported by the National Key R&D Program of China(Grant No.2020YFB1805405)the 111 Project(Grant No.B21049)+1 种基金the Foundation of Guizhou Provincial Key Laboratory of Public Big Data(Grant No.2019BDKFJJ014)the Fundamental Research Funds for the Central Universities,China(Grant No.2020RC38)。
文摘We propose an efficient quantum private comparison protocol firstly based on one direction quantum walks.With the help of one direction quantum walk,we develop a novel method that allows the semi-honest third party to set a flag to judge the comparing result,which improves the qubit efficiency and the maximum quantity of the participants’secret messages.Besides,our protocol can judge the size of the secret messages,not only equality.Furthermore,the quantum walks particle is disentangled in the initial state.It only requires a quantum walks operator to move,making our proposed protocol easy to implement and reducing the quantum resources.Through security analysis,we prove that our protocol can withstand well-known attacks and brute-force attacks.Analyses also reveal that our protocol is correct and practical.
基金This work was supported by National Natural Science Foundation of China(Grants Nos.61976053 and 61772134)Fujian Province Natural Science Foundation(Grant No.2018J01776)+1 种基金Program for New Century Excellent Talents in Fujian Province University,Probability and Statistics:Theory and Application(Grant No.IRTL1704)the Program for Innovative Research Team in Science and Technology in Fujian Province University.
文摘As an important branch of machine learning,clustering analysis is widely used in some fields,e.g.,image pattern recognition,social network analysis,information security,and so on.In this paper,we consider the designing of clustering algorithm in quantum scenario,and propose a quantum hierarchical agglomerative clustering algorithm,which is based on one dimension discrete quantum walk with single-point phase defects.In the proposed algorithm,two nonclassical characters of this kind of quantum walk,localization and ballistic effects,are exploited.At first,each data point is viewed as a particle and performed this kind of quantum walk with a parameter,which is determined by its neighbors.After that,the particles are measured in a calculation basis.In terms of the measurement result,every attribute value of the corresponding data point is modified appropriately.In this way,each data point interacts with its neighbors and moves toward a certain center point.At last,this process is repeated several times until similar data points cluster together and form distinct classes.Simulation experiments on the synthetic and real world data demonstrate the effectiveness of the presented algorithm.Compared with some classical algorithms,the proposed algorithm achieves better clustering results.Moreover,combining quantum cluster assignment method,the presented algorithm can speed up the calculating velocity.
文摘The present paper is focused on non-uniform quantum coins for the quantum random walk search algorithm. This is an alternative to the modification of the shift operator, which divides the search space into two parts. This method changes the quantum coins, while the shift operator remains unchanged and sustains the hypercube topology. The results discussed in this paper are obtained by both theoretical calculations and numerical simulations.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.11575087 and 11175087)
文摘We study the entanglement between the internal(coin)and the external(position)degrees of freedom in the dynamic and the static deterministic aperiodic quantum walks(QWs).For the dynamic(static)aperiodic QWs,the coin depends on the time(position)and takes two coins C(α)and C(β)arranged in the two classes of generalized Fibonacci(GF)and the Thue–Morse(TM)sequences.We found that for the dynamic QWs,the entanglement of three kinds of the aperiodic QWs are close to the maximal value,which are all much larger than that of the homogeneous QWs.Further,the first class of GF(1st GF)QWs can achieve the maximum entangled state,which is similar to that of the dynamic disordered QWs.And the entanglement of 1st GF QWs is greater than that of the TM QWs,being followed closely by the entanglement of the second class of GF(2nd GF)QWs.For the static QWs,the entanglement of three kinds of the aperiodic QWs are also close to the maximal value and 1st GF QWs can achieve the maximum entangled state.The entanglement of the TM QWs is between1st GF QWs and 2nd GF QWs.However,the entanglement of the static disordered QWs is less than that of three kinds of the aperiodic QWs.This is different from those of the dynamic QWs.From these results,we can conclude that the dynamic and static 1st GF QWs can also be considered as maximal entanglement generators.
基金Project supported by the National Natural Science Foundation of China(Grant No.61701139).
文摘In the optical quantum random walk system,phase nuctuation and Deam splitter uuctuation are two unavoldable decoherence factors.These two factors degrade the performance of quantum random walk by destroying coherence,and even degrade it into a classical one.We propose a scheme for the simulation of quantum random walk using phase shifters,tunable beam splitters,and photodetectors.This proposed scheme enables us to analyze the effect of phase fluctuation and beam splitter fluctuation on two-photon quantum random walk.Furthermore,it is helpful to guide the control of phase fluctuation and beam snlitter fluctuation in the exneriment.
基金Project supported by the National Basic Research Program of China(Grant No.2013CB338002)
文摘This study investigates the effects of systematic errors in phase inversions on the success rate and number of iterations in the optimized quantum random-walk search algorithm. Using the geometric description of this algorithm, a model of the algorithm with phase errors is established, and the relationship between the success rate of the algorithm, the database size, the number of iterations, and the phase error is determined. For a given database size, we obtain both the maximum success rate of the algorithm and the required number of iterations when phase errors are present in the algorithm. Analyses and numerical simulations show that the optimized quantum random-walk search algorithm is more robust against phase errors than Grover＇s algorithm.
基金supported by the Ministry of Science and Technology of Taiwan,China(Grant Nos.NSC-99-2112-M-032-002-MY3 and NSC 102-2112-M-032-003-MY3)the National Center for Theoretical Sciences(North)(NCTS-n)of China
文摘We present a numerical study of a model of quantum walk in a periodic potential on a line. We take the simple view that different potentials have different affects on the way in which the coin state of the walker is changed. For simplicity and definiteness, we assume that the walker＇s coin state is unaffected at sites without the potential, and rotated in an unbiased way according to the Hadamard matrix at sites with the potential. This is the simplest and most natural model of a quantum walk in a periodic potential with two coins. Six generic cases of such quantum walks are studied numerically. It is found that, of the six cases, four cases display significant localization effect where the walker is confined in the neighborhood of the origin for a sufficiently long time. Associated with such a localization effect is the recurrence of the probability of the walker returning to the neighborhood of the origin.
基金the National Natural Science Foundation of China(Grant Nos.10974192,11004029,and 11174052)the Natural Science Foundation of Jiangsu Province,China(Grant No.BK2010422)+2 种基金the Ph.D.Program of the Ministry of Education of Chinathe Excellent Young Teachers Program of Southeast University,Chinathe National Basic Research Program of China(Grant No.2011CB921203)
文摘Quantum walks act in obviously different ways from their classical counterparts, but decoherence will lessen and close this gap between them. To understand this process, it is necessary to investigate the evolution of quantum walks under different decoherence situations. In this article, we study a non-Markovian decoherent quantum walk on a line. In a short time regime, the behavior of the walk deviates from both ideal quantum walks and classical random walks. The position variance as a measure of the quantum walk collapses and revives for a short time, and tends to have a linear relation with time. That is, the walker’s behavior shows a diffusive spread over a long time limit, which is caused by non-Markovian dephasing affecting the quantum correlations between the quantum walker and his coin. We also study both quantum discord and measurement-induced disturbance as measures of the quantum correlations, and observe both collapse and revival in the short time regime, and the tendency to be zero in the long time limit. Therefore, quantum walks with non-Markovian decoherence tend to have diffusive spreading behavior over long time limits, while in the short time regime they oscillate between ballistic and diffusive spreading behavior, and the quantum correlation collapses and revives due to the memory effect.
基金Project supported by the National Natural Science Foundation of China(Grant Nos.11004029 and 11174052)the Natural Science Foundation of Jiangsu Province,China(Grant No.BK2010422)+3 种基金the Ph.D.Program of the Ministry of Education of Chinathe Excellent Young Teachers Program of Southeast University of Chinathe National Basic Research Program of China(Grant No.2011CB921203)the Open Fund from the State Key Laboratory of Precision Spectroscopy of East China Normal University
文摘This article aims to provide a review on quantum walks. Starting form a basic idea of discrete-time quantum walks, we will review the impact of disorder and decoherence on the properties of quantum walks. The evolution of the standard quantum walks is deterministic and disorder introduces randomness to the whole system and change interference pattern leading to the localization effect. Whereas, decoherence plays the role of transmitting quantum walks to classical random walks.
