Random Quantum Circuits are Approximate 2-designs
Tóm tắt
Given a universal gate set on two qubits, it is well known that applying random gates from the set to random pairs of qubits will eventually yield an approximately Haar-distributed unitary. However, this requires exponential time. We show that random circuits of only polynomial length will approximate the first and second moments of the Haar distribution, thus forming approximate 1- and 2-designs. Previous constructions required longer circuits and worked only for specific gate sets. As a corollary of our main result, we also improve previous bounds on the convergence rate of random walks on the Clifford group.
Tài liệu tham khảo
Aaronson, S.: Quantum Copy-Protection. Talk at QIP, New Delhi, India, December 2007, available at http://www.scottaaronson.com/talks/copy.ppt, 2007
Abeyesinghe, A., Devetak, I., Hayden, P., Winter, A.: The mother of all protocols: Restructuring quantum information’s family tree. http://arxiv.org/abs/:quant-ph/0606225v1, 2006
Ambainis, A., Emerson, E.: Quantum t-designs: t-wise independence in the quantum world. IEEE Conference on Computational Complexity 2007, http://arxiv.org/abs/:quant-ph/0701126v2, 2007
Ambainis, A., Mosca, M., Tapp, A., de Wolf, R.: Private Quantum Channels. FOCS 2000, Washington, DC: IEEE, 2000, pp. 547–553
Ambainis, A., Smith, A.: Small pseudo-random families of matrices: derandomizing approximate quantum encryption. Lecture Notes in Computer Science 3122, Berlin-Heidelberg-NewYork: Springer, 2004, pp. 249–260
Arnold, V.I., Krylov, A.L.: Uniform distribution of points on a sphere and some ergodic properties of solutions of linear ordinary differential equations in a complex domain. Sov. Math. Dokl. 4(1), 1962
Barenco A., Berthiaume A., Deutsch D., Ekert A., Jozsa R., Macchiavello C.: Stabilization of quantum computations by symmetrization. SIAM J. Comput. 26(5), 1541–1557 (1997)
Barnum, H.: Information-disturbance tradeoff in quantum measurement on the uniform ensemble and on the mutually unbiased bases. http://arxiv.org/abs/:quant-ph/0205155v1, 2002
Dahlsten O.C.O., Oliveira R., Plenio M.B.: The emergence of typical entanglement in two-party random processes. J. Phys. A Math. Gen. 40, 8081–8108 (2007)
Dankert, C., Cleve, R., Emerson, J., Livine, E.: Exact and approximate unitary 2-designs: constructions and applications. http://arxiv.org/abs/:quant-ph/0606161v1, 2006
Devetak I., Junge M., King C., Ruskai M.B.: Multiplicativity of completely bounded p-norms implies a new additivity result. Commun. Math. Phys. 266, 37–63 (2006)
Diaconis P., Saloff-Coste L.: Comparison theorems for reversible markov chains. Ann. Appl. Probab. 3(3), 696–730 (1993)
Diaconis P., Saloff-Coste L.: Logarithmic Sobolev inequalities for finite Markov chains. Ann. Appl. Probab. 6(3), 695–750 (1996)
DiVincenzo D., Leung D., Terhal B.: Quantum data hiding. Information Theory. IEEE Transactions 48(3), 580–598 (2002)
Emerson J., Livine E., Lloyd S.: Convergence conditions for random quantum circuits. Phys. Rev. A 72, 060302 (2005)
Goodman R., Wallach N.: Representations and Invariants of the Classical Groups. Cambridge University Press, Cambridge (1998)
Grimmett G., Welsh D.: Probability: An Introduction. Oxford University Press, Oxford (1986)
Gross D., Audenaert K., Eisert J.: Evenly distributed unitaries: On the structure of unitary designs. J. Math. Phys. 48, 052104 (2007)
Hallgren, S., Harrow, A.W.: Superpolynomial speedups based on almost any quantum circuit. In: Proc. 35th Intl. Colloq. on Automate Languages an Programming LCUS 5125, 2, pp. 782–795, 2008
Hayashi A., Hashimoto T., Horibe M.: Reexamination of optimal quantum state estimation of pure states. Phys. Rev. A 72, 032325 (2006)
Hayden P., Horodecki M., Yard J., Winter A.: A decoupling approach to the quantum capacity. Open Syst. Inf. Dyn. 15, 7–19 (2008)
Hayden P., Preskill J.: Black holes as mirrors: quantum information in random subsystems. JHEP 09, 120 (2007)
Hoory, S., Brodsky, A.: Simple Permutations Mix Even Better. http://arxiv.org/abs/math/0411098v2[math.CO] 2004
Kitaev A.Yu., Shen A.H., Vyalyi M.N.: Classical and Quantum Computation. RI Amer. Math. Soc., Providence (2002)
Montenegro R., Tetali P.: Mathematical aspects of mixing times in Markov chains. Found. Trends Theor. Comput. Sci. 1(3), 237–354 (2006)
Oliveira R., Dahlsten O.C.O., Plenio M.B.: Efficient generation of generic entanglement. Phys. Rev. Lett. 98, 130502 (2007)
Paulsen V.I.: Completely Bounded Maps and Dilations. John Wiley & Sons, Inc., New York (1987)
Sen, P.: Random measurement bases, quantum state distinction and applications to the hidden subgroup problem. IEEE Conference on Computational Complexity 2006, 2005, pp. 274–287
Watrous J.: Notes on super-operator norms induced by Schatten norms. Quantum Information and Computation 5(1), 58–68 (2005)
Znidaric M.: Optimal two-qubit gate for generation of random bipartite entanglement. Phys. Rev. A 76, 012318 (2007)