Fast quantum search driven by environmental engineering

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 $O(\sqrt{N})$ 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.     

基于散射量子行走的完全图上结构异常搜索算法

完全图K_N 上某个顶点连接到图G将破坏其对称性. 为加速定位这类结构异常, 基于散射量子行走模型设计搜索算法, 首先给出了算法酉算子的定义, 在此基础上利用完全图的对称性, 将算法的搜索空间限定为一个低维的坍缩图空间. 以G为一个顶点的情况为例, 利用硬币量子行走模型上的研究结论简化了坍缩图空间中酉算子的计算, 并借助矩阵扰动理论分析算法演化过程. 针对星图S_N 上结构异常的研究表明, 以星图中心节点为界将整个图分为左右两个部分, 当且仅当两部分在N→∞时具有相同的特征值, 搜索算法可以获得量子加速. 本文说明星图上的分析方法和结论可以推广至完全图的坍缩图上. 基于此, 本文证明无论完全图连接的图G结构如何, 搜索算法均可在O(√N) 时间内定位到目标顶点, 成功概率为1-O(1√N), 即量子行走搜索该类异常与经典搜索相比有二次加速.     

星图上的散射量子行走搜索算法

量子行走是一种典型的量子计算模型, 近年来开始受到量子计算理论研究者们的广泛关注. 本文首先证明了在星图上硬币量子行走与散射量子行走的酉等价关系, 之后提出了一个在星图上的散射量子行走搜索算法. 该算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时搜索成功概率大于Grover算法.     

Continuous-time quantum walks on star graphs

In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for N-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on K₂ graphs (complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.     

非马尔科夫环境中各向异性海森堡自旋链的量子失协

利用量子失协方法研究在非马尔科夫环境中具有时变磁场的两比特各向异性海森堡XYZ模型量子失协的动力学演化。海森堡XYZ系统的初始态为最大纠缠态 $\left|\psi_{A B}\right\rangle=(1 / \sqrt{2})(|11\rangle+|00\rangle)$ , 利用非马尔科夫量子态扩散方法解析求解非马尔科夫主方程, 得出系统的约化密度矩阵; 然后代入量子失协公式得出系统量子失协的演化动力学。讨论自旋耦合强度、环境关联系数γ和余弦磁场强度B对量子失协动力学的影响。研究发现: 当环境关联系数γ较小时, 系统的量子失协明显呈现上升趋势, 因此可以表明非马尔科夫环境具有增加系统量子失协的作用。同时较大的自旋耦合系数J和J_Z以及余弦磁场强度B也具有增加系统量子失协的作用。     

Search algorithm on strongly regular graphs based on scattering quantum walks

Janmark, Meyer, and Wong showed that continuous-time quantum walk search on known families of strongly regular graphs(SRGs) with parameters(N, k, λ, μ) achieves full quantum speedup. The problem is reconsidered in terms of scattering quantum walk, a type of discrete-time quantum walks. Here, the search space is confined to a low-dimensional subspace corresponding to the collapsed graph of SRGs. To quantify the algorithm's performance, we leverage the fundamental pairing theorem, a general theory developed by Cottrell for quantum search of structural anomalies in star graphs.The search algorithm on the SRGs with k scales as N satisfies the theorem, and results can be immediately obtained, while search on the SRGs with k scales as√N does not satisfy the theorem, and matrix perturbation theory is used to provide an analysis. Both these cases can be solved in O(√N) time steps with a success probability close to 1. The analytical conclusions are verified by simulation results on two SRGs. These examples show that the formalism on star graphs can be applied more generally.     

基于相位匹配的量子行走搜索算法及电路实现

量子行走是经典随机行走在量子力学框架下的对应, 理论上可以用来解决一类无序数据库的搜索问题. 因为携带信息的量子态的扩散速度与经典相比有二次方式的增长, 所以量子行走优于经典随机行走, 量子行走的特性值得加以利用. 量子行走作为一种新发现的物理现象的数学描述, 引发了一种新的思维方式, 孕育了一种新的理论计算模型. 最新研究表明, 量子行走本身也是一种通用计算模型, 可被视为设计量子算法的高级工具, 因此受到部分计算机理论科学领域学者的关注和研究. 对于多数问题求解方案的量子算法的设计, 理论上可以只在量子行走模型下进行考虑. 基于Grover算法的相位匹配条件, 本文提出了一个新的基于量子行走的搜索算法. 理论演算表明: 一般情况下本算法的时间复杂度与Grover算法相同, 但是当搜索的目标数目多于总数的1/3时, 本算法搜索成功的概率要大于Grover算法. 本文不但利用Grover算法中相位匹配条件构造了一个新的量子行走搜索算法, 而且在本研究室原有的量子电路设计研究成果的基础上给出了该算法的量子电路表述.     

Properties of field quantum entropy evolution in the Jaynes--Cummings model with initial squeezed coherent states field

The properties of the field quantum entropy evolution in a system of a single-mode squeezed coherent state field interacting with a two-level atom is studied by utilizing the complete quantum theory, and we focus our attention on the discussion of the influences of field squeezing parameter $\gamma $, atomic distribution angle $\theta $ and coupling strength $g$ between the field and the atom on the properties of the evolution of field quantum entropy. The results obtained from numerical calculation indicate that the amplitude of oscillation of field quantum entropy evolution decreases with the increasing of squeezing parameter $\gamma $, and that both atomic distribution angle $\theta $ and coupling strength $g$ between the field and the atom can influence the periodicity of field quantum entropy evolution.     

The effect of quantum noise on multiplayer quantum game

It has recently been realized that quantum strategies have a great advantage over classical ones in quantum games. However, quantum states are easily affected by the quantum noise, resulting in decoherence. In this paper, we investigate the effect of quantum noise on a multiplayer quantum game with a certain strategic space, with all players affected by the same quantum noise at the same time. Our results show that in a maximally entangled state, a special Nash equilibrium appears in the range of It has recently been realized that quantum strategies have a great advantage over classical ones in quantum games. However, quantum states are easily affected by the quantum noise, resulting in decoherence. In this paper, we investigate the effect of quantum noise on a multiplayer quantum game with a certain strategic space, with all players affected by the same quantum noise at the same time. Our results show that in a maximally entangled state, a special Nash equilibrium appears in the range of 0≤p≤0.622 （p is the quantum noise parameter）, and then disappears in the range of 0.622 〈 p≤ 1. Increasing the amount of quantum noise leads to the reduction of the quantum player＇s payoff.     

Scattering Solutions in Networks of Thin Fibers: Small Diameter Asymptotics

Small diameter asymptotics is obtained for scattering solutions in a network of thin fibers. The asymptotics is expressed in terms of solutions of related problems on the limiting quantum graph Γ . We calculate the Lagrangian gluing conditions at vertices for the problems on the limiting graph. If the frequency of the incident wave is above the bottom of the absolutely continuous spectrum, the gluing conditions are formulated in terms of the scattering data for each individual junction of the network. The authors were supported partially by the NSF grant DMS-0405927.     

清华物理系量子信息研究的新进展

在清华大学物理系成立60周年之际,我们对近年来清华大学物理系量子信息研究的主要进展情况作一介绍,包括量子搜索算法研究,核磁共振量子计算的实验研究,量子通讯的理论与实验研究.在量子搜索算法研究方面,我们提出了量子搜索算法的相位匹配,纠正了当时的一种错误观点,并且提出了一种成功率为100%的量子搜索算法,改进了Grover算法;在核磁共振量子计算实验方面,我们实现了2到7个量子比特的多种量子算法的实验演示;在量子通讯方面,我们提出了分布式传输的量子通讯的思想,应用于量子密钥分配、量子秘密共享、量子直接安全通讯等方面,构造了多个量子通讯的理论方案.在实验室,我们实现了2米距离的空间量子密码通讯的演示实验.     

Optimized quantum random-walk search algorithm for multi-solution search

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.     

Uncertainty Relation between Detection Probability and Energy Fluctuations

A classical random walker starting on a node of a finite graph will always reach any other node since the search is ergodic, namely it fully explores space, hence the arrival probability is unity. For quantum walks, destructive interference may induce effectively non-ergodic features in such search processes. Under repeated projective local measurements, made on a target state, the final detection of the system is not guaranteed since the Hilbert space is split into a bright subspace and an orthogonal dark one. Using this we find an uncertainty relation for the deviations of the detection probability from its classical counterpart, in terms of the energy fluctuations.     

Large Communities in a Scale-Free Network

We prove the existence of a large complete subgraph w.h.p. in a preferential attachment random graph process with an edge-step. That is, we consider a dynamic stochastic process for constructing a graph in which at each step we independently decide, with probability \(p\in (0,1)\), whether the graph receives a new vertex or a new edge between existing vertices. The connections are then made according to a preferential attachment rule. We prove that the random graph \(G_{t}\) produced by this so-called generalized linear preferential (GLP) model at time t contains a complete subgraph whose vertex set cardinality is given by \(t^\alpha \), where \(\alpha = (1-\varepsilon )\frac{1-p}{2-p}\), for any small \(\varepsilon >0\) asymptotically almost surely.     

Embedded graph invariants in Chern-Simons theory

Chern-Simons gauge theory, since its inception as a topological quantum field theory, has proved to be a rich source of understanding for knot invariants. In this work the theory is used to explore the definition of the expectation value of a network of Wilson lines — an embedded graph invariant. Using a generalization of the variational method, lowest-order results for invariants for graphs of arbitrary valence and general vertex tangent space structure are derived. Gauge invariant operators are introduced. Higher order results are found. The method used here provides a Vassiliev-type definition of graph invariants which depend on both the embedding of the graph and the group structure of the gauge theory. It is found that one need not frame individual vertices. However, without a global projection of the graph there is an ambiguity in the relation of the decomposition of distinct vertices. It is suggested that framing may be seen as arising from this ambiguity — as a way of relating frames at distinct vertices.     

Quantum walk search algorithm for multi-objective searching with iteration auto-controlling on hypercube

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 multi-objective 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_{\rm f}=(\pi /2)\sqrt{2^{n-2}} $.     

Finding tree symmetries using continuous-time quantum walk

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.     

Graph State-Based Quantum Secret Sharing with the Chinese Remainder Theorem

Quantum secret sharing (QSS) is a significant quantum cryptography technology in the literature. Dividing an initial secret into several sub-secrets which are then transferred to other legal participants so that it can be securely recovered in a collaboration fashion. In this paper, we develop a quantum route selection based on the encoded quantum graph state, thus enabling the practical QSS scheme in the small-scale complex quantum network. Legal participants are conveniently designated with the quantum route selection using the entanglement of the encoded graph states. Each participant holds a vertex of the graph state so that legal participants are selected through performing operations on specific vertices. The Chinese remainder theorem (CRT) strengthens the security of the recovering process of the initial secret among the legal participants. The security is ensured by the entanglement of the encoded graph states that are cooperatively prepared and shared by legal users beforehand with the sub-secrets embedded in the CRT over finite fields.     

Dynamics on quantum graphs as constrained systems

We study the possibility of regarding the dynamics on a quantum graph as limit, as a small parameter ∈ → O, of a dynamics with a strong confining potential. We define a projection operator along the first eigenfunction of a transversal operator and, under suitable assumptions, we prove that the projection of the solution strongly converges along subsequences to a function that satisfies the Schrödinger equation on each open edge of the graph. Moreover the limit dynamics is unitary. If the limit is independent of the subsequence, one has a limit one-parameter group, generated by one of the self-adjoint extensions of a symmetric operator defined on the open graph (with the vertices deleted). The crucial role of the shape of the confining potential at the vertices is pointed out.