logo

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

A survey on quantum computing

More info
  • ReceivedApr 5, 2016
  • AcceptedMay 31, 2016

Abstract


Funded by

国家自然科学基金(61222202)

国家自然科学基金(61433014)

国家自然科学基金(61502449)


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