SCIENTIA SINICA Informationis, Volume 46, Issue 8: 982-1002(2016) https://doi.org/10.1360/N112016-00084

## A survey on quantum computing

• AcceptedMay 31, 2016
Share
Rating

### Abstract

On the basis of its unrivalled potential to solve factorization problems and further application in cryptography, quantum computing is considered as one of the most promising computational models for the future. It provides a new angle for thinking of computation and a new approach for attack various computationally difficult problems. In this article, we give a comprehensive survey of developments in the last twenty years on quantum algorithms, quantum complexity, quantum programming theory, quantum circuits, and quantum cryptography that we hope will serve as references for researchers in related fields. We also outline various research directions and open problems in this area, with the hope of prompting further progress or even solutions.

### References

[1] Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc Royal Soc A-Math Phys Eng Sci, 1985, 400: 97-117 CrossRef Google Scholar

[2] Bernstein E, Vazirani U. Quantum complexity theory. SIAM J Comput, 1997, 26: 1411-1473 CrossRef Google Scholar

[3] Yao A C-C. Quantum circuit complexity. In: Proceedings of the 34th Annual Symposium on Foundations of Computer Science, Palo Alto, 1993. 352-361. Google Scholar

[4] Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Proc Royal Soc A-Math Phys Eng Sci, 1992, 439: 553-558 CrossRef Google Scholar

[5] Simon D R. On the power of quantum computation. SIAM J Comput, 1997, 26: 1474-1483 CrossRef Google Scholar

[6] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 1994. 124-134. Google Scholar

[7] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing. New York: ACM, 1996. 212-219. Google Scholar

[8] Ambainis A. Quantum walk algorithm for element distinctness. SIAM J Comput, 2007, 37: 210-239 CrossRef Google Scholar

[9] Brassard G, H{\o}yer P, Mosca M, et al. Quantum amplitude amplification and estimation. Quant Comput Inf, 2002, 305: 53-74. Google Scholar

[10] Harrow A, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Phys Rev Lett, 2009, 15: 150502. Google Scholar

[11] Lloyd S, Mohseni M, Rebentrost P. Quantum algorithms for supervised and unsupervised machine learning. arXiv: 1307.0411. Google Scholar

[12] Hoyer P, Lee T, Spalek R. Negative weights make adversaries stronger. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing. New York: ACM, 2007. 526-535. Google Scholar

[13] Reichardt B W. Reflections for quantum query algorithms. In: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia: Society for Industrial and Applied Mathematics, 2011. 560-569. Google Scholar

[14] Jain R, Ji Z F, Upadhyay S, et al. QIP = PSPACE. J ACM, 2011, 58: 30. Google Scholar

[15] Vazirani U, Vidick T. Fully device independent quantum key distribution. Phys Rev Lett, 2014, 113: 140501-74 CrossRef Google Scholar

[16] Miller C A, Shi Y Y. Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing. New York: ACM, 2014. 417-426. Google Scholar

[17] Gill J. Computational complexity of probabilistic Turing machines. SIAM J Comput, 1977, 6: 675-695 CrossRef Google Scholar

[18] Lloyd S. Universal quantum simulators. Science, 1996, 273: 1073-695 CrossRef Google Scholar

[19] Bernstein E, Vazirani U. Quantum complexity theory. SIAM J Comput, 1997, 26: 1411-1473 CrossRef Google Scholar

[20] Adleman L, de Marrais J, Huang M-D. Quantum computability. SIAM J Comput, 1997 26: 1524-1540. Google Scholar

[21] Watrous J. Succinct quantum proofs for properties of finite groups. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, 2000. 537-546. Google Scholar

[22] Bennett C H, Bernstein E, Brassard G, et al. Strengths and weaknesses of quantum computing. SIAM J Comput, 1997, 26: 1510-1523 CrossRef Google Scholar

[23] Aaronson S, Shi Y Y. Quantum lower bounds for the collision and the element distinctness problems. J ACM, 2004, 51: 595-605 CrossRef Google Scholar

[24] Aaronson S. Quantum computing, postselection, and probabilistic polynomial time. Proc Royal Soc London A: Math Phys Eng Sci, 2005, 461: 3473-3482 CrossRef Google Scholar

[25] Aharonov D, Jones V, Landau Z. A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 2009, 55: 395-421 CrossRef Google Scholar

[26] Freedman M, Larsen M, Wang Z. A modular functor which is universal for quantum computation. Commun Math Phys, 2002, 227: 605-622 CrossRef Google Scholar

[27] Wocjan P, Zhang S Y. Several natural BQP-Complete problems. arXiv:quant-ph/0606179. Google Scholar

[28] Aaronson S, Ambainis A. Forrelation: a problem that optimally separates quantum from classical computing. In: Proceedings of the 47th Annual ACM on Symposium on Theory of Computing. New York: ACM, 2015. 307-316. Google Scholar

[29] Buhrman H, de Wolf R. Complexity measures and decision tree complexity: a survey. Theor Comput Sci, 2002, 288: 21-43 CrossRef Google Scholar

[30] Yao A C-C. Some complexity questions related to distributive computing (preliminary report). In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing. New York: ACM, 1979. 209-213. Google Scholar

[31] SunX M, Yao A C-C. On the quantum query complexity of local search in two and three dimensions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, 2006. 429-438. Google Scholar

[32] Ambainis A, Balodis K, Belovs A, et al. Separations in query complexity based on pointer functions. arXiv:1506.04719. Google Scholar

[33] Aaronson S, Ben-David S, Kothari R. Separations in query complexity using cheat sheets. arXiv: 1511.01937. Google Scholar

[34] Beals R, Buhrman H, Cleve R, et al. Quantum lower bounds by polynomials. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, 1998. 352-361. Google Scholar

[35] Ambainis A. Superlinear advantage for exact quantum algorithms. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing. New York: ACM, 2013. 891-900. Google Scholar

[36] Ambainis A, Gruska J, Zheng S G. Exact quantum algorithms have advantage for almost all Boolean functions. Quant Inf Comput, 2015, 15: 435-452. Google Scholar

[37] Baianu I. Organismic supercategories and qualitative dynamics of systems. Bulletin Math Biophys, 1971, 33: 339-354 CrossRef Google Scholar

[38] Baianu I. Categories, functors and quantum automata theory. In: Proceedings of the 4th International Congress of Logic, Methodology and Philosophy of Science, Bucharest, 1971. Google Scholar

[39] Kondacs A, Watrous J. On the power of quantum finite state automata. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Miami Beach, 1997. 66-75. Google Scholar

[40] Ambainis A, Freivalds R. 1-way quantum finite automata: strengths, weaknesses and generalizations. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, 1998. 332-341. Google Scholar

[41] Ambainis A, Nahimovs N. Improved constructions of quantum automata. Theor Comput Sci, 2009, 410: 1916-1922 CrossRef Google Scholar

[42] Ambainis A, Watrous J. Two-way finite automata with quantum and classical states. Theor Comput Sci, 2002, 287: 299-311 CrossRef Google Scholar

[43] Moore C, Crutchfield J P. Quantum automata and quantum grammars. Theor Comput Sci, 2000, 237: 275-306 CrossRef Google Scholar

[44] Li L Z, Qiu D W. Determining the equivalence for one-way quantum finite automata. Theor Comput Sci, 2008, 403: 42-51 CrossRef Google Scholar

[45] Mateus P, Qiu D W, Li L Z. On the complexity of minimizing probabilistic and quantum automata. Inf Comput, 2012, 218: 36-53 CrossRef Google Scholar

[46] Qiu D W, Li L Z, Mateus P, et al. Exponentially more concise quantum recognition of non-RMM languages. J Comput Syst Sci, 2015, 81: 359-375 CrossRef Google Scholar

[47] Kitaev A Y, Shen A, Vyalyi M N. Classical and Quantum Computation. Providence: American Mathematical Society, 2002. Google Scholar

[48] Knill E. Quantum randomness and nondeterminism. arXiv:quant-ph/9610012. Google Scholar

[49] Aharonov D, Gottesman D, Irani S, et al. The power of quantum systems on a line. Commun Math Phys, 2009, 287: 41-65 CrossRef Google Scholar

[50] Liu Y K. Consistency of local density matrices is QMA-complete. In: Approximation, randomization, and Combinatorial Optimization. Algorithms and Techniques. Berlin: Springer, 2006. 438-449. Google Scholar

[51] Watrous J. Succinct quantum proofs for properties of finite groups. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, 2000. 537-546. Google Scholar

[52] Watrous J. Quantum computational complexity. In: Encyclopedia of Complexity and Systems Science. New York: Springer, 2009. 7174-7201. Google Scholar

[53] Harrow A W, Montanaro A. Testing product states, quantum Merlin-Arthur games and tensor optimization. J ACM, 2013, 60: 3. Google Scholar

[54] Li K, Smith G. Quantum de Finetti theorem under fully-one-way adaptive measurements. Phys Rev Lett, 2015, 114: 160503-65 CrossRef Google Scholar

[55] Schwarz M. An exponential time upper bound for quantum Merlin-Arthur games with unentangled provers. arXiv:1510.08447. Google Scholar

[56] WatrousJ . PSPACE has constant-round quantum interactive proof systems. Theor Comput Sci, 2003, 292: 575-588 CrossRef Google Scholar

[57] Kitaev A, Watrous J. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In: Proceedings of the 32nd Annual ACM Symposium on Theory of Computing. New York: ACM, 2000. 608-617. Google Scholar

[58] ItoT, Kobayashi H, Preda D, et al. Generalized Tsirelson inequalities, commuting-operator provers, and multi-prover interactive proof systems. In: Proceedings of IEEE Conference on Computational Complexity, College Park, 2008. 187-198. Google Scholar

[59] Ito T, Kobayashi H, Watrous J. Quantum interactive proofs with weak error bounds. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. New York: ACM, 2012. 266-275. Google Scholar

[60] Fitzsimons J, Vidick T. A multiprover interactive proof system for the local Hamiltonian problem. In: Proceedings of the Conference on Innovations in Theoretical Computer Science. New York: ACM, 2015. 103-112. Google Scholar

[61] Natarajan A, Vidick T. Constant-soundness interactive proofs for local Hamiltonians. arXiv:1512.02090. Google Scholar

[62] JiZ F. Classical verification of quantum proofs. arXiv:1505.07432. Google Scholar

[63] AmbainisA , Childs A M, Reichardt B, et al. Any AND-OR formula of size N can be evaluated in time N 1/2+o(1) on a quantum computer. SIAM J Comput, 2010, 39: 2513-2530 CrossRef Google Scholar

[64] Santha M. On the Monte Carlo boolean decision tree complexity of read-once formulae. Random Struct Algorithm, 1995, 6: 75-87 CrossRef Google Scholar

[65] Buhrman H, Durr C, Heiligman M, et al. Quantum algorithms for element distinctness. SIAM J Comput, 2005, 34: 1324-1330 CrossRef Google Scholar

[66] MagniezF, Santha M, Szegedy M. Quantum algorithms for the triangle problem. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, Vancouver, 2005. 1109-1117. Google Scholar

[67] Magniez F, Santha M, Szegedy M. Quantum algorithms for the triangle problem. SIAM J Comput, 2007, 37: 413-424 CrossRef Google Scholar

[68] Belovs A. Span programs for functions with constant-sized 1-certificates: extended abstract. In: Proceedings of the 44th Symposium on Theory of Computing. New York: ACM, 2012. 77-84. Google Scholar

[69] LeeT, Magniez F, Santha M. Improved quantum query algorithms for triangle finding and associativity testing. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 2013. 1486-1502. Google Scholar

[70] Jeffery S, Kothari R, Magniez F. Nested quantum walks with quantum data structures. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 2013. 1474-1485. Google Scholar

[71] SunX M, Yao A C-C, Zhang S Y. Graph properties and circular functions: how low can quantum query complexity go? In: Proceedings of the 19th IEEE Conference on Computational Complexity, Amherst, 2004. 286-293. Google Scholar

[72] Belovs A, Rosmanis A. On the power of non-adaptive learning graphs. In: Proceedings of the 28th Conference on Computational Complexity, Stanford, 2013. 44-55. Google Scholar

[73] Le Gall. Improved quantum algorithm for triangle finding via combinatorial arguments. In: Proceedings of the 55th Annual Symposium on Foundations of Computer Science, Philadelphia, 2014. 216-225. Google Scholar

[74] Ambainis A. Quantum walk algorithm for element distinctness. SIAM J Comput, 2007, 37: 210-239 CrossRef Google Scholar

[75] Belovs A. Learning-graph-based quantum algorithm for k-distinctness. In: Proceedings of the 53rd Annual Symposium on Foundations of Computer Science, New Brunswick, 2012. 207-216. Google Scholar

[76] Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation. Contemp Math, 2002, 305: 53-74 CrossRef Google Scholar

[77] Schoning T. A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, New York City, 1999. 410-414. Google Scholar

[78] Durr C, Hoyer P. A quantum algorithm for finding the minimum. arXiv:quant-ph/9607014. Google Scholar

[79] Dürr C, Heiligman M, H{\o}yer P, et al. Quantum query complexity of some graph problems. In: Automata, Languages and Programming. Berlin Springer, 2004. 481-493. Google Scholar

[80] Ramesh H, Vinay V. String matching in O(n+m) quantum time. J Discrete Algorithms, 2003, 1: 103-110 CrossRef Google Scholar

[81] Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Phys Rev Lett, 2009, 103: 150502-110 CrossRef Google Scholar

[82] Lloyd S, Mohseni M, Rebentrost P. Quantum algorithms for supervised and unsupervised machine learning. arXiv:1307.0411. Google Scholar

[83] Rebentrost P, Mohseni M, Lloyd S. Quantum support vector machine for big data classification. Phys Rev Lett, 2014, 113: 130503-110 CrossRef Google Scholar

[84] Wiebe N, Braun D, Lloyd S. Quantum Algorithm for Data Fitting. Phys Rev Lett, 2012, 109: 050505-110 CrossRef Google Scholar

[85] Garnerone S, Zanardi P, Lidar D A. Adiabatic Quantum Algorithm for Search Engine Ranking. Phys Rev Lett, 2012, 108: 230506-110 CrossRef Google Scholar

[86] Clader B D, Jacobs B C, Sprouse C R. Preconditioned Quantum Linear System Algorithm. Phys Rev Lett, 2013, 110: 250504-110 CrossRef Google Scholar

[87] Farhi E, Goldstone J, Gutmann S, et al. Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106. Google Scholar

[88] van Dam W, Mosca M, Vazirani U. How Powerful is Adiabatic Quantum Computation? In: Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, 2001. 279-287. Google Scholar

[89] King J, Yarkoni S, Nevisi M M, et al. Benchmarking a quantum annealing processor with the time-to-target metric. arXiv:1508.05087. Google Scholar

[90] Feynman R. Simulating physics with computers. Int J Theor Phys, 1982, 21: 467-488 CrossRef Google Scholar

[91] Lloyd S. Universal quantum simulators. Science, 1996, 273: 1073-1078 CrossRef Google Scholar

[92] Berry D W, Childs A M. Black-box Hamiltonian simulation and unitary implementation. Quant Inf Comput, 2012, 12: 29-62. Google Scholar

[93] Aaronson S, Arkhipov A. The computational complexity of linear optics. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. New York: ACM, 2011. 333-342. Google Scholar

[94] BroomeM A, Fedrizzi A, Rahimi-Keshari S, et al. Photonic boson sampling in a tunable circuit. Science, 2013, 339: 794-798 CrossRef Google Scholar

[95] CrespiA , Osellame R, Ramponi R, et al. Integrated multimode interferometers with arbitrary designs for photonic boson sampling. Nature Photonics, 2013, 7: 545-549 CrossRef Google Scholar

[96] Ralph T C. Quantum computation: Boson sampling on a chip. Nature Photonics, 2013, 7: 514-515 CrossRef Google Scholar

[97] Spring J B, Metcalf B J, Humphreys P C, et al. Boson sampling on a photonic chip. Science, 2013, 339: 798-801 CrossRef Google Scholar

[98] Knill E H. Conventions for Quantum Pseudo-Code. LANL report LAUR-96-2724. 1996. Google Scholar

[99] Omer B. A procedure formalism for quantum computing. Dissertation for Ph.D. Degree. Vienna: Technical University of Vienna, 1998. Google Scholar

[100] Sanders J W, Zuliani P. Quantum computing. In: Proceedings of Mathematics of Program Construction, LNCS, Ponte de Lima, 2000. 1837: 80-99. Google Scholar

[101] Bettelli S, Calarco T, Serafini L. Toward an architecture for quantum programming. arXic:cs.PL/0103009. Google Scholar

[102] Selinger P. Towards a quantum programming language. Math Struct Comput Sci, 2004, 14: 527-586 CrossRef Google Scholar

[103] Sabry A. Modeling quantum computing in Haskell. In: Proceedings of the ACM SIGPLAN Workshop on Haskell. New York: ACM, 2003. 39-49. Google Scholar

[104] Valiron B. A functional programming language for quantum computation with classical control. Dissertation for Master's Degree. Ottawa: University of Ottawa, 2004. Google Scholar

[105] Altenkirch T, Grattage J. A functional quantum programming language. In: Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science, Chicago, 2005. 249-258. Google Scholar

[106] Ying M S. Foundations of quantum programing. In: Proceedings of the 8th Asian Conference on Programming Languages and Systems. New York: ACM, 2016. 16-20. Google Scholar

[107] Valiron B, Ross N J, Selinger P, et al. Programming the quantum future. Commun ACM, 2015, 58: 52-61. Google Scholar

[108] Abramsky S. High-level methods for quantum computation and information. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, Turku, 2004. 410-414. Google Scholar

[109] Abramsky S, Coecke B. A categorical semantics of quantum protocols. In: Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, Turku, 2004. 415-425. Google Scholar

[110] van Tonder A. A Lambda calculus for quantum computation. SIAM J Comput, 2004, 33: 1109-1135 CrossRef Google Scholar

[111] Petersen A, Oskin M. A new algebraic foundation for quantum programming languages. In: Proceedings of the 2nd Workshop on Non-Silicon Computing at ISCA, San Diego, 2003. 88: 3544-3549. Google Scholar

[112] GirardJ-Y. Between logic and quantic: a tract. Linear Logic Comput Sci, 2004, 316: 346-381. Google Scholar

[113] Gay S J, Nagarajan R. Communicating quantum processes. In: Proceedings of the 32nd ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages. New York: ACM, 2005. 145-157. Google Scholar

[114] LalireM . Relations among quantum processes: bisimilarity and congruence. Math Struct Comput Sci, 2006, 16: 407-428 CrossRef Google Scholar

[115] Ying M. Floyd-Hoare logic for quantum programs. ACM Trans Program Lang Syst, 2011, 33: 19. Google Scholar

[116] FengY, Duan R Y, Ying M S. Bisimulation for quantum processes. ACM Trans Program Lang Syst, 2012, 34: 17. Google Scholar

[117] Ying M S, Feng Y. Quantum loop programs. Acta Inform, 2010, 47: 221-250 CrossRef Google Scholar

[118] BennettC H, Brassard G. Quantum cryptography: public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing. New York: IEEE Press, 1984. 175-179. Google Scholar

[119] Mayers D. Unconditional security in quantum cryptography. J ACM, 2001, 48: 351-406 CrossRef Google Scholar

[120] Shor P W, Preskill J. Simple proof of security of the BB84 quantum key distribution protocol. Phys Rev Lett, 2000, 85: 441-444 CrossRef Google Scholar

[121] Bennett C H, Bessette F, Brassard G, et al. Experimental quantum cryptography. J Cryptol, 1998, 5: 3-28. Google Scholar

[122] MayersD, Yao A. Quantum cryptography with imperfect apparatus. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, Palo Alto, 1998. 503-509. Google Scholar

[123] ColbeckR. Quantum and relativistic protocols for secure multi-party computation. Dissertation for Ph.D. Degree. Cambridge: University of Cambridge, 2006. Google Scholar

[124] Lo H K, Curty M, Qi B. Measurement-device-independent quantum key distribution. Phys Rev Lett, 2012, 108: 130503-28 CrossRef Google Scholar

[125] Pirandola S, Ottaviani C, Spedalieri G, et al. High-rate measurement-device-independent quantum cryptography. Nat Photon, 2015, 9: 397-402 CrossRef Google Scholar

[126] Sasaki T, Yamamoto Y, Koashi M. Practical quantum key distribution protocol without monitoring signal disturbance. Nature, 2014, 509: 475-478 CrossRef Google Scholar

[127] Nauerth S, Moll F, Rau M, et al. Air-to-ground quantum communication. Nature Photonics, 2013, 7: 382-386 CrossRef Google Scholar

[128] Sasaki T, Yamamoto Y, Koashi M. Practical quantum key distribution protocol without monitoring signal disturbance. Nature, 2014, 509: 475-386 CrossRef Google Scholar

[129] Guan J-Y, Cao Z, Liu Y, et al. Experimental passive round-robin differential phase-shift quantum key distribution. Phys Rev Lett, 2015, 114: 180502-386 CrossRef Google Scholar

[130] WangS , Yin Z-Q, Chen W, et al. Experimental demonstration of a quantum key distribution without signal disturbance monitoring. Nature Photonics, 2015, 9: 832-836 CrossRef Google Scholar

[131] Gao F, Guo F-Z, Wen Q-Y, et al. Comment on experimental demonstration of a quantum protocol for Byzantine agreement and liar detection". Phys Rev Lett, 2008, 101: 208901-836 CrossRef Google Scholar

[132] Gao F, Wen Q-Y, Zhu F-C. Teleportation attack on the QSDC protocol with a random basis and order. Chinese Phys B, 2008, 17: 3189-3193 CrossRef Google Scholar

[133] Barenco A, Bennett C H, Cleve R, et al. Elementary gates for quantum computation. Phys Rev A, 1995, 52: 3457-3467 CrossRef Google Scholar

[134] CalderbankA R, Shor P W. Good quantum error-correcting codes exist. Phys Rev A, 1996, 54: 1098-1105 CrossRef Google Scholar

[135] Shende V V, Markov I L, Bullock S S. Minimal universal two-qubit controlled-NOT-based circuits. Phys Rev A, 2004, 69: 062321-1105 CrossRef Google Scholar

[136] Shende V V, Prasad A K, Markov I L, et al. Synthesis of reversible logic circuits. IEEE Trans Comput-Aided Design Integr Circ Syst, 2003, 22: 710-722 CrossRef Google Scholar

[137] Yang G, Song X, Hung W N N, et al. Bi-directional synthesis of 4-bit reversible circuits. Comput J, 2008, 51: 207-215. Google Scholar

[138] Golubitsky O, Falconer S M, Maslov D. Synthesis of the optimal 4-bit reversible circuits. In: Proceedings of the 47th Design Automation Conference. New York: ACM, 2010. 653-656. Google Scholar

[139] Hung W, Song X, Yang G, et al. Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans Comput-Aided Des Integr Circ Syst, 2006, 25: 1652-1663 CrossRef Google Scholar

[140] Grosse D, Wille R, Dueck G, et al. Exact multiple-control Toffoli network synthesis with SAT techniques. IEEE Trans Comput-Aided Des Integr Circ Syst, 2009, 28: 703-715 CrossRef Google Scholar

[141] Aaronson S, Gottesman D. Improved simulation of stabilizer circuits. Phys Rev A, 2004, 70: 052328-715 CrossRef Google Scholar

[142] Patel K N, Markov I L, Hayes J P. Optimal synthesis of linear reversible circuits. Quant Inf Comput, 2008, 8: 282-294. Google Scholar

[143] Maslov D. Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Phys Rev A, 2007, 76: 052310-294 CrossRef Google Scholar

[144] Miller D M, Maslov D, Dueck G W. A transformation based algorithm for reversible logic synthesis. In: Proceedings of the 40th Annual Design Automation Conference. New York: ACM, 2003. 318-323. Google Scholar

[145] Maslov D, Dueck G W, Miller D M. Techniques for the synthesis of reversible Toffoli networks. ACM Trans Des Autom Electron Sys, 2007, 12: 1-28. Google Scholar

[146] Gupta P, Agrawal A, Jha N K. An algorithm for synthesis of reversible logic circuits. IEEE Trans Comput-Aided Des Integr Circ Syst, 2006, 25: 2317-2330 CrossRef Google Scholar

[147] Donald J, Jha N K. Reversible logic synthesis with Fredkin and Peres gates. J Emerg Tech Comput Syst, 2008, 4: 1-19. Google Scholar

[148] Saeedi M, Zamani M S, Sedighi M, et al. Reversible circuit synthesis using a cycle-based approach. J Emerg Tech Comput Syst, 2010, 6: 1-26. Google Scholar

[149] Peng F, Xie G J. Optimum design of quantum teleportation circuit. J Appl Sci, 2010, 28: 313-317 [彭斐, 解光军. 量子隐形传态电路的优化设计. 应用科学学报, 2010, 28: 313-317]. Google Scholar

[150] Yang G, Song X, Hung W N, et al. Group theory based synthesis of binary reversible circuits. Lec Notes Comput Sci, 2006, 3959: 365-374 CrossRef Google Scholar

[151] DiVincenzoD P, Smolin J A. Results on two-bit gate design for quantum computers. In: Proceedings of the Workshop on Physics and Computation, Dallas, 1994. 14-23. Google Scholar

[152] Yu N, Duan R, Ying M. Five two-qubit gates are necessary for implementing the Toffoli gate. Phys Rev A, 2013, 88: 010304-374 CrossRef Google Scholar

[153] SongG, Klappenecker A. The simplified Toffoli gate implementation by Margolus is optimal. QIC, 2004, 4: 361-372. Google Scholar

[154] Shende V V, Markov I L. On the CNOT-cost of TOFFOLI gates. Quant Inf Comput, 2009, 9: 461-486. Google Scholar

[155] Bocharov A, Svore K M. Resource-optimal single-qubit quantum circuits. Phys Rev Lett, 2012, 109: 190501-486 CrossRef Google Scholar

[156] Bocharov A, Gurevich Y, Svore K M. Efficient decomposition of single-qubit gates into V basis circuits. Phys Rev A, 2013, 88: 012313-486 CrossRef Google Scholar

[157] Bocharov A, Roetteler M, Svore K M. Efficient synthesis of universal repeat-until-success quantum circuits. Phys Rev Lett, 2015, 114: 080502-486 CrossRef Google Scholar

[158] Ross N J, Selinger P. Optimal ancilla-free Clifford+T approximation of $z$-rotations. arXiv:1403.2975. Google Scholar

[159] Selinger P. Generators and relations for n-qubit Clifford operators. arXiv:1310.6813. Google Scholar

[160] Selinger P. Efficient Clifford+T approximation of single-qubit operators. Quant Inf Comput, 2012, 15: 159-180. Google Scholar

[161] Maslov D. Reversible logic synthesis benchmarks page. http://www.cs.uvic.ca/dmaslov. 2011. Google Scholar

[162] Wille R, Grosse D, Teuber L, et al. RevLib: an online resource for reversible functions and reversible circuits. In: Proceedings of the 38th International Symposium on Multiple Valued Logic, Dallas, 2008. 220-225. Google Scholar

[163] Soeken M, Frehse S, Wille R, et al. RevKit: a toolkit for reversible circuit design. Multiple-Valued Logic Soft Comput, 2012, 18: 55-65. Google Scholar

[164] Shi Y-Y, Duan L-M, Vidal G. Classical simulation of quantum many-body systems with atree tensor network. Phys Rev A, 2006, 74: 022320-65 CrossRef Google Scholar

[165] Babai L. Graph isomorphism in quasipolynomial time. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing. New York: ACM, 2016. 684-697. Google Scholar

[166] Mosca M. Quantum computer algorithms. Dissertation for Ph.D. Degree. Oxford: University of Oxford, 1999. Google Scholar

[167] AmbainisA. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In: Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science, Paris, 2012. 636-647. Google Scholar

[168] Le GallF. Quantum complexity of Boolean matrix multiplication and related problems. In: Computing With New Resources. Berlin: Springer, 2014. 176-191. Google Scholar

[169] Qiu D W, Zheng S G. Characterizations of symmetrically partial Boolean functions with exact quantum query complexity. arXiv: 1603.06505. Google Scholar

Citations

• #### 0

Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有