We establish a thorough treatment of reduced-state synchronization for qubit networks with the aim of driving the qubits’ reduced states to a common trajectory. The evolution of the quantum network’s state is described by a master equation, where the network Hamiltonian is either a direct sum or a tensor product of identical qubit Hamiltonians, and the coupling terms are given by a set of permutation operators over the network. The permutations introduce naturally quantum directed interactions. We show that reduced-state synchronization is achieved if and only if the quantum interaction graphs corresponding to the permutation operators form a strongly connected union graph. The proof is based on an algebraic analysis making use of the Perron-Frobenius theorem for non-negative matrices. The convergence rate and the limiting orbit are explicitly characterized. Numerical examples are provided illustrating the obtained results. Further, we investigate the missing symmetry in the reduced-state synchronization from a graphical point of view. The information-flow hierarchy in quantum permutation operators is characterized by different layers of information-induced graphs. We show that the quantum synchronization equation is by nature equivalent to several parallel cut-balanced consensus processes, and a necessary and sufficient condition is obtained for quantum reduced-state synchronization under switching interactions applying recent work of Hendrickx and Tsitsiklis.
Scientific interest on consensus and synchronization subject to the laws of quantum mechanics has also been noticed. Recent work @cite_33 introduced the measures of synchronization in quantum systems of coupled Harmonic oscillators. Sepulchre @cite_5 generalized consensus algorithms to non-commutative spaces and presented convergence results for quantum stochastic maps to a fully mixed state. Mazzarella @cite_21 made a systematic study of consensus-seeking in quantum networks, where four classes of consensus quantum states based on invariance and symmetry properties were introduced and a quantum gossip algorithm @cite_9 was proposed for reaching a symmetric consensus state over a quantum network. The class of quantum gossip algorithms was extended to symmetrization problems in a group-theoretic framework in @cite_3 .
@cite_33 @cite_9 @cite_21 @cite_3 @cite_5
1998162358 2117905067 1972462360 166500159 2119455667
This paper extends the consensus framework, widely studied in the literature on distributed computing and control algorithms, to networks of quantum systems. We define consensus situations on the basis of invariance and symmetry properties, finding four different generalizations of classical consensus states. This new viewpoint can be directly used to study consensus for probability distributions, as these can be seen as a particular case of quantum statistical states: in this light, our analysis is also relevant for classical problems. We then extend the gossip consensus algorithm to the quantum setting and prove it converges to symmetric states while preserving the expectation of permutation-invariant global observables. Applications of the framework and the algorithms to estimation and control problems on quantum networks are discussed. In this paper, we propose and study a master-equation based approach to drive a quantum network with @math qubits to a consensus (symmetric) state introduced by The state evolution of the quantum network is described by a Lindblad master equation with the Lindblad terms generated by continuous-time swapping operators, which also introduce an underlying interaction graph. We establish a graphical method that bridges the proposed quantum consensus scheme and classical consensus dynamics by studying an induced graph (with @math nodes) of the quantum interaction graph (with @math qubits). A fundamental connection is then shown that quantum consensus over the quantum graph is equivalent to componentwise classical consensus over the induced graph, which allows various existing works on classical consensus to be applicable to the quantum setting. Some basic scaling and structural properties of the quantum induced graph are established via combinatorial analysis. Necessary and sufficient conditions for exponential and asymptotic quantum consensus are obtained, respectively, for switching quantum interaction graphs. As a quantum analogue of classical synchronization of coupled oscillators, quantum synchronization conditions are also presented, in which the reduced states of all qubits tend to a common trajectory. In this paper, we investigate the convergence of the state of a quantum network to a consensus (symmetric) state. The state evolution of the quantum network with continuous-time swapping operators can be described by a Lindblad master equation, which also introduces an underlying interaction graph for the network. For a fixed quantum interaction graph, we prove that the state of a quantum network with continuous-time Markovian dynamics converges to a consensus state, with convergence rate given by the smallest nonzero eigenvalue of a matrix serving as the Laplacian of the quantum interaction graph. We show that this convergence rate can be optimized via standard convex programming given a fixed amount of edge weights. For switching quantum interaction graphs, we establish necessary and sufficient conditions for exponential quantum consensus and asymptotic quantum consensus, respectively. The convergence analysis is based on a bridge built between the proposed quantum consensus scheme and classical consensus dynamics, in that quantum consensus of n qubits naturally defines a consensus process on an induced classical graph with 22n nodes. Existing consensus results on classical networks can thus be adopted to establish the quantum consensus convergence. AbstractIn this paper we propose a continuous-time, dissipative Markov dynamics that asymp-totically drives a network of n-dimensional quantum systems to the set of states that areinvariant under the action of the subsystem permutation group. The Lindblad-type gen-erator of the dynamics is built with two-body subsystem swap operators, thus satisfyinglocality constraints, and preserve symmetric observables. The potential use of the pro-posed generator in combination with local control and measurement actions is illustratedwith two applications: the generation of a global pure state and the estimation of thenetwork size. 1 INTRODUCTION Classical consensus algorithms and the related distributed control problems have recentlygenerated an impressive body of literature, motivated by applications in distributed com-putation and multi-agent coordination, see e.g. [1, 2, 3, 4, 5, 6, 7, 8, 9]. We have recentlyrecast the problem, and a class of algorithms for its solution, as a dynamical symmetriza-tion problem in a group-theoretic framework [10]. This allows to extend the use of simpleand robust algorithms, e.g. of gossip type [11], to new settings and applications. Amongthese, we have studied a quantum version of consensus problems and its applications [12],which can be seen as symmetrization with respect to the subsystem-permutation group, aswell as control methods like quantum dynamical decoupling [13], in which we generally donot have a multipartite structure and symmetrization is attained with respect to other ﬁnitegroups. The emerging dynamics are intrinsically in discrete time, and suitable for sequentialimplementation in dissipative quantum simulators [14]. This paper interprets and generalizes consensus-type algorithms as switching dynamics leading to symmetrization with respect to the actions of a finite group. Explicit convergence results are provided in a grouptheoretic formulation, both for deterministic and for stochastic dynamics. We show how the symmetrization framework directly extends the scope of consensustype algorithms and results to applications as diverse as consensus on probability distributions (either classical or quantum), computation of the discrete Fourier transform, uniform random state generation, and openloop disturbance rejection by quantum dynamical decoupling. This indicates a way to extend the desirable robustness of consensus-inspired algorithms to even more fields of application. Convergence analysis of consensus algorithms is revisited in the light of the Hilbert distance. The Lyapunov function used in the early analysis by Tsitsiklis is shown to be the Hilbert distance to consensus in log coordinates. Birkhoff theorem, which proves contraction of the Hilbert metric for any positive homogeneous monotone map, provides an early yet general convergence result for consensus algorithms. Because Birkhoff theorem holds in arbitrary cones, we extend consensus algorithms to the cone of positive definite matrices. The proposed generalization finds applications in the convergence analysis of quantum stochastic maps, which are a generalization of stochastic maps to non-commutative probability spaces. We introduce and characterize two different measures which quantify the level of synchronization of coupled continuous variable quantum systems. The two measures allow us to extend to the quantum domain the notions of complete and phase synchronization. The Heisenberg principle sets a universal bound to complete synchronization. The measure of phase synchronization is, in principle, unbounded; however, in the absence of quantum resources (e.g., squeezing) the synchronization level is bounded below a certain threshold. We elucidate some interesting connections between entanglement and synchronization and, finally, discuss an application based on quantum optomechanical systems. PREFACE ACKNOWLEDGEMENTS PART 1: PROBABILITY IN CLASSICAL AND QUANTUM MECHANICS 1. Classical probability theory and stochastic processes 2. Quantum Probability PART 2: DENSITY MATRIX THEORY 3. Quantum Master Equations 4. Decoherence PART 3: STOCHASTIC PROCESSES IN HILBERT SPACE 5. Probability distributions on Hilbert space 6. Stochastic dynamics in Hilbert space 7. The stochastic simulation method 8. Applications to quantum optical systems PART 4: NON-MARKOVIAN QUANTUM PROCESSES 9. Projection operator techniques 10. Non-Markovian dynamics in physical systems PART 5: RELATIVISTIC QUANTUM PROCESSES 11. Measurements in relativistic quantum mechanics 12. Open quantum electrodynamics It is well understood that the use of quantum entanglement significantly enhances the computational power of systems. Much of the attention has focused on Bell states and their multipartite generalizations. However, in the multipartite case it is known that there are several inequivalent classes of states, such as those represented by the W-state and the GHZ-state. Our main contribution is a demonstration of the special computational power of these states in the context of paradigmatic problems from classical distributed computing. Concretely, we show that the W-state is the only pure state that can be used to exactly solve the problem of leader election in anonymous quantum networks. Similarly we show that the GHZ-state is the only one that can be used to solve the problem of distributed consensus when no classical post-processing is considered. These results generalize to a family of W- and GHZ-like states. At the heart of the proofs of these impossibility results lie symmetry arguments. We present a scalable quantum algorithm to solve binary consensus in a system of n crash-prone quantum processes. The algorithm works in O(polylog n) time sending O(n polylog n) qubits against the adaptive adversary. The time performance of this algorithm is asymptotically better than a lower bound Ω(√n log n) on time of classical randomized algorithms against adaptive adversaries. Known classical randomized algorithms having each process send O(polylog n) messages work only for oblivious adversaries. Our quantum algorithm has a better time performance than deterministic solutions, which have to work in Ω(t) time for t < n failures. Algorithms such as quantum factoring1 and quantum search2 illustrate the great theoretical promise of quantum computers; but the practical implementation of such devices will require careful consideration of the minimum resource requirements, together with the development of procedures to overcome inevitable residual imperfections in physical systems3,4,5. Many designs have been proposed, but none allow a large quantum computer to be built in the near future6. Moreover, the known protocols for constructing reliable quantum computers from unreliable components can be complicated, often requiring many operations to produce a desired transformation3,4,5,7,8. Here we show how a single technique—a generalization of quantum teleportation9—reduces resource requirements for quantum computers and unifies known protocols for fault-tolerant quantum computation. We show that single quantum bit (qubit) operations, Bell-basis measurements and certain entangled quantum states such as Greenberger–Horne–Zeilinger (GHZ) states10—all of which are within the reach of current technology—are sufficient to construct a universal quantum computer. We also present systematic constructions for an infinite class of reliable quantum gates that make the design of fault-tolerant quantum computers much more straightforward and methodical. A novel class of hybrid quantum-classical algorithms based on the variational approach have recently emerged from separate proposals addressing, for example, quantum chemistry and combinatorial problems. These algorithms provide an approximate solution to the problem at hand by encoding it in the state of a quantum computer. The operations used to prepare the state are not a priori fixed but, quite the opposite, are subjected to a classical optimization procedure that modifies the quantum gates and improves the quality of the approximate solution. While the quantum hardware determines the size of the problem and what states are achievable (limited, respectively, by the number of qubits and by the kind and number of possible quantum gates), it is the classical optimization procedure that determines the way in which the quantum states are explored and whether the best available solution is actually reached. In addition, the quantities required in the optimization, for example the objective function itself, have to be estimated with finite precision in any experimental implementation. While it is desirable to have very precise estimates, this comes at the cost of repeating the state preparation and measurement multiple times. Here we analyze the competing requirements of high precision and low number of repetitions and study how the overall performance of the variational algorithm is affected by the precision level and the choice of the optimization method. Finally, this study introduces quasi-Newton optimization methods in the general context of hybrid variational algorithms and presents quantitative results for the Quantum Approximate Optimization Algorithm. Abstract Quantum entanglement is the most surprising feature of quantum mechanics. Entanglement is simultaneously responsible for the difficulty of simulating quantum matter on a classical computer and the exponential speedups afforded by quantum computers. Ground states of quantum many-body systems typically satisfy an “area law”: The amount of entanglement between a subsystem and the rest of the system is proportional to the area of the boundary. A system that obeys an area law has less entanglement and can be simulated more efficiently than a generic quantum state whose entanglement could be proportional to the total system’s size. Moreover, an area law provides useful information about the low-energy physics of the system. It is widely believed that for physically reasonable quantum systems, the area law cannot be violated by more than a logarithmic factor in the system’s size. We introduce a class of exactly solvable one-dimensional physical models which we can prove have exponentially more entanglement than suggested by the area law, and violate the area law by a square-root factor. This work suggests that simple quantum matter is richer and can provide much more quantum resources (i.e., entanglement) than expected. In addition to using recent advances in quantum information and condensed matter theory, we have drawn upon various branches of mathematics such as combinatorics of random walks, Brownian excursions, and fractional matching theory. We hope that the techniques developed herein may be useful for other problems in physics as well. We introduce a problem of distinguishing between two quantum states as a new underlying problem to build a computational cryptographic scheme that is ”secure” against quantum adversary. Our problem is a natural generalization of the distinguishability problem between two probability distributions, which are commonly used in computational cryptography. More precisely, our problem QSCDff is the computational distinguishability problem between two types of random coset states with a hidden permutation over the symmetric group. We show that (i) QSCDff has the trapdoor property; (ii) the average-case hardness of QSCDff coincides with its worst-case hardness; and (iii) QSCDff is at least as hard in the worst case as the graph automorphism problem. Moreover, we show that QSCDff cannot be efficiently solved by any quantum algorithm that naturally extends Shor's factorization algorithm. These cryptographic properties of QSCDff enable us to construct a public-key cryptosystem, which is likely to withstand any attack of a polynomial-time quantum adversary. Preface. Part I: Gathering the Tools. 1. Introduction to Quantum Physics. 2. Quantum Tests. 3. Complex Vector Space. 4. Continuous Variables. Part II: Cryptodeterminism and Quantum Inseparability. 5. Composite Systems. 6. Bell's Theorem. 7. Contextuality. Part III: Quantum Dynamics and Information. 8. Spacetime Symmetries. 9. Information and Thermodynamics. 10. Semiclassical Methods. 11. Chaos and Irreversibility. 12. The Measuring Process. Author Index. Subject Index. Preface Acknowledgement Nomenclature and notation Part I. Fundamental Concepts: 1. Introduction and overview 2. Introduction to quantum mechanics 3. Introduction to computer science Part II. Quantum Computation: 4. Quantum circuits 5. The quantum Fourier transform and its applications 6. Quantum search algorithms 7. Quantum computers: physical realisation Part III. Quantum Information: 8. Quantum noise, open quantum systems, and quantum operations 9. Distance measurement for quantum information 10. Quantum error-correction 11. Entropy and information 12. Quantum information theory Appendix A. Notes on basic probability theory Appendix B. Group theory Appendix C. Approximating quantum gates: the Solvay-Kitaev theorem Appendix D. Number theory Appendix E. Public-key cryptography and the RSA cryptosystem Appendix F. Proof of Lieb's theorem References Index. This paper provides a theoretical framework for analysis of consensus algorithms for multi-agent networked systems with an emphasis on the role of directed information flow, robustness to changes in network topology due to link node failures, time-delays, and performance guarantees. An overview of basic concepts of information consensus in networks and methods of convergence and performance analysis for the algorithms are provided. Our analysis framework is based on tools from matrix theory, algebraic graph theory, and control theory. We discuss the connections between consensus problems in networked dynamic systems and diverse applications including synchronization of coupled oscillators, flocking, formation control, fast consensus in small-world networks, Markov processes and gossip-based algorithms, load balancing in networks, rendezvous in space, distributed sensor fusion in sensor networks, and belief propagation. We establish direct connections between spectral and structural properties of complex networks and the speed of information diffusion of consensus algorithms. A brief introduction is provided on networked systems with nonlocal information flow that are considerably faster than distributed systems with lattice-type nearest neighbor interactions. Simulation results are presented that demonstrate the role of small-world effects on the speed of consensus algorithms and cooperative control of multivehicle formations Although a quantum state requires exponentially many classical bits to describe, the laws of quantum mechanics impose severe restrictions on how that state can be accessed. This paper shows in three settings that quantum messages have only limited advantages over classical ones. First, we show that BQP qpoly is contained in PP poly, where BQP qpoly is the class of problems solvable in quantum polynomial time, given a polynomial-size "quantum advice state" that depends only on the input length. This resolves a question of Buhrman, and means that we should not hope for an unrelativized separation between quantum and classical advice. Underlying our complexity result is a general new relation between deterministic and quantum one-way communication complexities, which applies to partial as well as total functions. Second, we construct an oracle relative to which NP is not contained in BQP qpoly. To do so, we use the polynomial method to give the first correct proof of a direct product theorem for quantum search. This theorem has other applications; for example, it can be used to fix a flawed result of Klauck about quantum time-space tradeoffs for sorting. Third, we introduce a new trace distance method for proving lower bounds on quantum one-way communication complexity. Using this method, we obtain optimal quantum lower bounds for two problems of Ambainis, for which no nontrivial lower bounds were previously known even for classical randomized protocols. The question has remained open if near-term gate model quantum computers will offer a quantum advantage for practical applications in the pre-fault tolerance noise regime. A class of algorithms which have shown some promise in this regard are the so-called classical-quantum hybrid variational algorithms. Here we develop a low-depth quantum algorithm to train quantum Boltzmann machine neural networks using such variational methods. We introduce a method which employs the quantum approximate optimization algorithm as a subroutine in order to approximately sample from Gibbs states of Ising Hamiltonians. We use this approximate Gibbs sampling to train neural networks for which we demonstrate training convergence for numerically simulated noisy circuits with depolarizing errors of rates of up to 4 . Quantum correlations between two particles show nonclassical properties that can be used for providing secure transmission of information. We present a quantum cryptographic system in which users store particles in a transmission center, where their quantum states are preserved using quantum memories. Correlations between the particles stored by two users are created upon request by projecting their product state onto a fully entangled state. Our system allows for secure communication between any pair of users who have particles in the same center. Unlike other quantum cryptographic systems, it can work without quantum channels and it is suitable for building a quantum cryptographic network. We also present a modified system with many centers. 1996 The American Physical Society.