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.展开更多
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)(?).展开更多
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.展开更多
量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺...量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺正变换的硬币算符与迁移算符,构建了DTQW搜索算法步骤框图,在此基础上,应用SKW搜索算法对4节点无向图中的标记节点态进行搜索,通过态塌缩的观测,实现以1/4概率化读取出目标节点。研究结果表明,当有n个足够大的量子系统,并保持彼此之间的强纠缠性时,量子随机行走可以过渡到经典随机行走。文章还详细讨论了DTQW搜索算法实现左右同移的二次加速搜索机制。展开更多
Studies have demonstrated that a joined complete graph is a typical mathematical model that can support a fast quantum search. In this paper, we study the implementation of joined complete graphs in atomic systems and...Studies have demonstrated that a joined complete graph is a typical mathematical model that can support a fast quantum search. In this paper, we study the implementation of joined complete graphs in atomic systems and realize a quantum search of runtime ■ based on this implementation with a success probability of 50%. Even though the practical systems inevitably interact with the surrounding environment, we reveal that a successful quantum search can be realized through delicately engineering the environment itself. We consider that our study will bring about a feasible way to realize quantum information processing including quantum algorithms in reality.展开更多
Game theory problems are widely applied in many research areas such as computer science and finance,with the key issue being how to quickly make decisions.Here,we present a novel quantum algorithm for game theory prob...Game theory problems are widely applied in many research areas such as computer science and finance,with the key issue being how to quickly make decisions.Here,we present a novel quantum algorithm for game theory problems based on a continuous quantum walk.Our algorithm exhibits quantum advantage compared to classical game algorithms.Furthermore,we exploit the analogy between the wave function of the Schrodinger equation and the voltage in Kirchhoff's law to effectively translate the design of quantum game trees into classical circuit networks.We have theoretically simulated the quantum game trees and experimentally validated the quantum functionality speedup on classical circuit networks.Due to the robust scalability and stability inherent in classical circuit networks,quantum game trees implemented within this framework hold promise for addressing more intricate application scenarios.展开更多
为探究多比特量子算法在量子芯片和模拟器中的实现现状,分别在IBM量子芯片和模拟器上运行Grover搜索算法、量子随机行走算法以及量子傅里叶变换算法。针对2 bit Grover搜索算法和2 bit量子随机行走算法,分析测量次数对运行结果的影响并...为探究多比特量子算法在量子芯片和模拟器中的实现现状,分别在IBM量子芯片和模拟器上运行Grover搜索算法、量子随机行走算法以及量子傅里叶变换算法。针对2 bit Grover搜索算法和2 bit量子随机行走算法,分析测量次数对运行结果的影响并选用最高可模拟次数对量子芯片和模拟器的运算结果进行比对。设计并运行5 bit量子傅里叶变换算法和3 bit Grover搜索算法,分别采用IBM Q模拟器进行最高次数的模拟。实验结果表明,量子芯片测试结果并没有随测量次数的增加而优化,模拟器计算结果的准确度明显优于量子芯片。展开更多
In recent years, rapid developments of quantum computer are witnessed in both the hardware and the algorithm domains, making it necessary to have an updated review of some major techniques and applications in quantum ...In recent years, rapid developments of quantum computer are witnessed in both the hardware and the algorithm domains, making it necessary to have an updated review of some major techniques and applications in quantum algorithm design.In this survey as well as tutorial article, the authors ?rst present an overview of the development of quantum algorithms, then investigate ?ve important techniques: Quantum phase estimation, linear combination of unitaries, quantum linear solver, Grover search, and quantum walk, together with their applications in quantum state preparation, quantum machine learning, and quantum search. In the end, the authors collect some open problems in?uencing the development of future quantum algorithms.展开更多
文摘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 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 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.
文摘量子行走得益于概率幅的叠加特性,可同时出现在多条路径中,使其能以平方式乃至指数级别的速度加速扩散所携带的量子信息。文章基于无向图G=(V,E)结构,从离散时间量子随机行走(Discrete Time Quantum Walk,DTQW)搜索算法特性出发,运用幺正变换的硬币算符与迁移算符,构建了DTQW搜索算法步骤框图,在此基础上,应用SKW搜索算法对4节点无向图中的标记节点态进行搜索,通过态塌缩的观测,实现以1/4概率化读取出目标节点。研究结果表明,当有n个足够大的量子系统,并保持彼此之间的强纠缠性时,量子随机行走可以过渡到经典随机行走。文章还详细讨论了DTQW搜索算法实现左右同移的二次加速搜索机制。
基金supported by the National Key R&D Program of China(Grant No.2017YFA0303800)the National Natural Science Foundation of China(Grant Nos.11604014 and 11974046)。
文摘Studies have demonstrated that a joined complete graph is a typical mathematical model that can support a fast quantum search. In this paper, we study the implementation of joined complete graphs in atomic systems and realize a quantum search of runtime ■ based on this implementation with a success probability of 50%. Even though the practical systems inevitably interact with the surrounding environment, we reveal that a successful quantum search can be realized through delicately engineering the environment itself. We consider that our study will bring about a feasible way to realize quantum information processing including quantum algorithms in reality.
基金supported by the National Key R&D Program of China under grant no.2022YFA1404900the National Natural Science Foundation of China(12234004 and 12374323).
文摘Game theory problems are widely applied in many research areas such as computer science and finance,with the key issue being how to quickly make decisions.Here,we present a novel quantum algorithm for game theory problems based on a continuous quantum walk.Our algorithm exhibits quantum advantage compared to classical game algorithms.Furthermore,we exploit the analogy between the wave function of the Schrodinger equation and the voltage in Kirchhoff's law to effectively translate the design of quantum game trees into classical circuit networks.We have theoretically simulated the quantum game trees and experimentally validated the quantum functionality speedup on classical circuit networks.Due to the robust scalability and stability inherent in classical circuit networks,quantum game trees implemented within this framework hold promise for addressing more intricate application scenarios.
文摘为探究多比特量子算法在量子芯片和模拟器中的实现现状,分别在IBM量子芯片和模拟器上运行Grover搜索算法、量子随机行走算法以及量子傅里叶变换算法。针对2 bit Grover搜索算法和2 bit量子随机行走算法,分析测量次数对运行结果的影响并选用最高可模拟次数对量子芯片和模拟器的运算结果进行比对。设计并运行5 bit量子傅里叶变换算法和3 bit Grover搜索算法,分别采用IBM Q模拟器进行最高次数的模拟。实验结果表明,量子芯片测试结果并没有随测量次数的增加而优化,模拟器计算结果的准确度明显优于量子芯片。
基金supported partially by the National Natural Science Foundation of China under Grant No.11671388CAS Project QYZDJ-SSW-SYS022GF S&T Innovation Special Zone Project
文摘In recent years, rapid developments of quantum computer are witnessed in both the hardware and the algorithm domains, making it necessary to have an updated review of some major techniques and applications in quantum algorithm design.In this survey as well as tutorial article, the authors ?rst present an overview of the development of quantum algorithms, then investigate ?ve important techniques: Quantum phase estimation, linear combination of unitaries, quantum linear solver, Grover search, and quantum walk, together with their applications in quantum state preparation, quantum machine learning, and quantum search. In the end, the authors collect some open problems in?uencing the development of future quantum algorithms.
