在本研究中估計對SHA2-512使用量子搜尋演算法進行量子原像攻擊所需要的代價，並計算加入表面碼架構的量子容錯後所需的代價。
我們使用量子編程軟體LIQUi |>，來設計SHA2-512的可逆量子電路，並使用量子搜尋演算法對SHA2-512進行量子原像攻擊，計算出大約需要5.055×10^83的空間複雜度、2.245×10^83的時間複雜度以及5953個物理量子位元；加入量子容錯後，大約需要5.654×10^90的空間複雜度、5.651×10^90的時間複雜度以及1.17×10^8個物理量子位元，容錯前後相比較後，空間複雜度約為10^7.4倍；時間複雜度約為10^7倍；物理量子位元約為10^4.3倍。

In this study, we estimate the cost of using quantum search algorithm to perform quantum preimage attacks on SHA2-512, and calculate the cost of adding quantum fault tolerance to the surface code architecture.
We use the quantum programming software LIQUi |> to design the reversible quantum circuit of SHA2-512, and use the quantum search algorithm to perform quantum preimage attacks on SHA2-512, and calculate approximately 〖5.055×10〗^83 space complexity, requires approximately 〖2.245×10〗^83 time complexity and 5953 physical qubits. After adding quantum fault tolerance, requires approximately〖5.654×10〗^90 space complexity, 〖5.651×10〗^90 time complexity and 〖1.17×10〗^8 physical qubits.Comparing the before and after, the space complexity is about 10^7.4 times; the time complexity is about 10^7times; the physical qubit is about 10^4.3times.

[1] Keyes, Robert W. "The impact of Moore's Law." IEEE solid-state circuits society newsletter 11.3 (2006): 25-27.
[2] Ladd, T.D., et al., Quantum computers. Nature, 2010. 464: p. 45.
[3] Sobti, Rajeev, and G. Geetha. "Cryptographic hash functions: a review." International Journal of Computer Science Issues (IJCSI) 9.2 (2012): 461.
[4] Ebrahim, Mansoor, Shujaat Khan, and Umer Bin Khalid. "Symmetric algorithm survey: a comparative analysis." arXiv preprint arXiv:1405.0398 (2014).
[5] Kovalenko, I. N., and A. I. Kochubinskii. "Asymmetric cryptographic algorithms." Cybernetics and systems analysis 39.4 (2003): 549-554.
[6] Primitives, A. E. S. "Advanced Encryption Standard (AES)(FIPS-197)." (2003).
[7] Yanofsky, Noson S., and Mirco A. Mannucci. Quantum computing for computer scientists. Cambridge University Press, 2008.p195~p203
[8] Giri, Pulak Ranjan, and Vladimir E. Korepin. "A review on quantum search algorithms." Quantum Information Processing 16.12 (2017): 315.
[9] Luan, Linlin, Zhijie Wang, and Sanming Liu. "Progress of Grover Quantum Search Algorithm." Energy Procedia 16 (2012): 1701-1706.
[10] Mutibara, A. B., and R. Refianti. "Simulation of Grover algorithm Quantum search in a Classical Computer." International Journal of computer Scince and Information security 8.9 (2010).
[11] Kaliski, Burt. PKCS# 1: RSA encryption version 1.5. RFC 2313, March, 1998.
[12] Hwang, Ren-Junn, et al. "An efficient decryption method for RSA cryptosystem." 19th International Conference on Advanced Information Networking and Applications (AINA'05) Volume 1 (AINA papers). Vol. 1. IEEE, 2005.
[13] O’Dwyer, James. "Quantum Computing and Shor’s Quantum Factoring Algorithm: A Review." Journal of Young Investigators 3 (2001).
[14] Takahashi, Yasuhiro, and Noboru Kunihiro. "A quantum circuit for shor's factoring algorithm using 2n+ 2 qubits." Quantum Information & Computation 6.2 (2006): 184-192.
[15] Lomonaco, S. J. "Shor's quantum factoring algorithm." Proceedings of Symposia in Applied Mathematics. Vol. 58. 2002.
[16] Lavor, C., L. R. U. Manssur, and R. Portugal. "Shor's Algorithm for Factoring Large Integers." arXiv preprint quant-ph/0303175 (2003).
[17] Fowler, Austin G., Simon J. Devitt, and Lloyd CL Hollenberg. "Implementation of Shor's algorithm on a linear nearest neighbour qubit array." arXiv preprint quant-ph/0402196 (2004).
[18] Amy, Matthew, et al. "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3." International Conference on Selected Areas in Cryptography. Springer, Cham, 2016.
[19] https://en.wikipedia.org/wiki/Quantum_decoherence
[20] Iriyama, Satoshi, Masanori Ohya, and Igor Volovich. "Generalized quantum Turing machine and its application to the SAT chaos algorithm." Quantum Information and Computing. 2006. 204-225.
[21] Aliferis, Panos, and Andrew W. Cross. "Subsystem fault tolerance with the Bacon-Shor code." Physical review letters 98.22 (2007): 220502.
[22] Steane, Andrew M. "Error correcting codes in quantum theory." Physical Review Letters 77.5 (1996): 793.
[23] Steane, Andrew M. "Enlargement of calderbank-shor-steane quantum codes." IEEE Transactions on Information Theory 45.7 (1999): 2492-2495.
[24] Bravyi, Sergey B., and A. Yu Kitaev. "Quantum codes on a lattice with boundary." arXiv preprint quant-ph/9811052 (1998).
[25] Yanofsky, Noson S., and Mirco A. Mannucci. Quantum computing for computer scientists. Cambridge University Press, 2008.p171~p178
[26] Collins, David, K. W. Kim, and W. C. Holton. "Deutsch-Jozsa algorithm as a test of quantum computation." Physical Review A 58.3 (1998): R1633.
[27] Gulde, Stephan, et al. "Implementation of the Deutsch–Jozsa algorithm on an ion-trap quantum computer." Nature 421.6918 (2003): 48-50.
[28] Yanofsky, Noson S., and Mirco A. Mannucci. Quantum computing for computer scientists. Cambridge University Press, 2008.p187~p194
[29] Simon, D.R., "On the power of quantum computation", Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on: 116–123, retrieved 2011-06-06
[30] Nielsen, Michael A., and Isaac L. Chuang. "Quantum computation and quantum information." Phys. Today 54 (2001): 60-2.p216~p247.
[31] Williams, Colin P. Explorations in quantum computing. Springer Science & Business Media, 2010.p140-150
[32] Williams, Colin P. Explorations in quantum computing. Springer Science & Business Media, 2010.p151~p161
[33] Li, Hai-Sheng, et al. "The multi-level and multi-dimensional quantum wavelet packet transforms." Scientific reports 8.1 (2018): 1-23.
[34] Yao, Xi-Wei, et al. "Quantum image processing and its application to edge detection: theory and experiment." Physical Review X 7.3 (2017): 031041.
[35] Li, Hai-Sheng, et al. "Multidimensional color image storage, retrieval, and compression based on quantum amplitudes and phases." Information Sciences 273 (2014): 212-232.
[36] Nielsen, Michael A., and Isaac Chuang. "Quantum computation and quantum information." (2002): 558-559.p309~p324.
[37] Esteve, Daniel, Jean-Michel Raimond, and Jean Dalibard. Quantum entanglement and information processing: lecture notes of the Les Houches Summer School 2003. Elsevier, 2004.p443~p558.
[38] Hirose, Masashi, and Paola Cappellaro. "Coherent feedback control of a single qubit in diamond." Nature 532.7597 (2016): 77-80.
[39] Maurand, R., et al. "A CMOS silicon spin qubit." Nature communications 7.1 (2016): 1-6.
[40] Nigg, Daniel, et al. "Quantum computations on a topologically encoded qubit." Science 345.6194 (2014): 302-305.
[41] https://qiskit.org/documentation/install.html
[42] https://docs.microsoft.com/en-us/quantum/?view=qsharp-preview
[43] http://docs.rigetti.com/en/stable/start.html
[44] Steiger, Damian S., Thomas Häner, and Matthias Troyer. "ProjectQ: an open source software framework for quantum computing." Quantum 2 (2018): 49.
[45] LaRose, Ryan. "Overview and comparison of gate level quantum software platforms." Quantum 3 (2019): 130.
[46] Parent, Alex, Martin Roetteler, and Krysta M. Svore. "Reversible circuit compilation with space constraints." arXiv preprint arXiv:1510.00377 (2015).
[47] Amy, Matthew, et al. "Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3." International Conference on Selected Areas in Cryptography. Springer, Cham, 2016.
[48] Roffe, Joschka. "Quantum error correction: an introductory guide." Contemporary Physics 60.3 (2019): 226-245.
[49] Williams, Colin P. Explorations in quantum computing. Springer Science & Business Media, 2010.p51~p122.
[50] https://en.wikipedia.org/wiki/Black-box_testing
[51] https://en.wikipedia.org/wiki/Oracle_machine
[52] Stinson, Douglas Robert, and Maura Paterson. Cryptography: theory and practice. CRC press, 2018.chapter 5.
[53] Wang, Xiaoyun, Hongbo Yu, and Yiqun Lisa Yin. "Efficient collision search attacks on SHA-0." Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 2005.
[54] Wang, Xiaoyun, et al. "Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD." IACR Cryptol. ePrint Arch. 2004 (2004): 199.
[55] Stevens, Marc, et al. "Announcing the first SHA1 collision." Google Security Blog (2017).
[56] Standard, Secure Hash. "Federal Information Processing Standard (FIPS) 180-2." National Institute of Science and Technology (2002).
[57] https://zh.wikipedia.org/wiki/SHA-2
[58] Landauer, Rolf. "Irreversibility and heat generation in the computing process." IBM journal of research and development 5.3 (1961): 183-191.
[59] Toffoli, Tommaso. "Reversible computing." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 1980.
[60] Monz, Thomas, et al. "Realization of the quantum Toffoli gate with trapped ions." Physical review letters 102.4 (2009): 040501.
[61] Williams, Colin P. Explorations in quantum computing. Springer Science & Business Media, 2010.p66~p67.
[62] Wecker, Dave, and Krysta M. Svore. "LIQUi|>: A software design architecture and domain-specific language for quantum computing." arXiv preprint arXiv:1402.4467 (2014).
[63] Parent, Alex, Martin Roetteler, and Krysta M. Svore. "REVS: A tool for space-optimized reversible circuit synthesis." International Conference on Reversible Computation. Springer, Cham, 2017.
[64] 李颖, and 孙昌璞. "通用量子计算机和容错量子计算——概念, 现状和展望." 物理 48.8 (2019): 477-487.
[65] Nielsen, Michael A., and Isaac Chuang. "Quantum computation and quantum information." (2002): 558-559.p453~p472.
[66] Fowler, Austin G., Adam C. Whiteside, and Lloyd CL Hollenberg. "Towards practical classical processing for the surface code." Physical review letters 108.18 (2012): 180501.
[67] Kubica, Aleksander, and Rafal Demkowicz-Dobrzanski. "Using Quantum Metrological Bounds in Quantum Error Correction: A Simple Proof of the Approximate Eastin-Knill Theorem." arXiv preprint arXiv:2004.11893 (2020).
[68] Campbell, Earl T., and Mark Howard. "Magic state parity-checker with pre-distilled components." Quantum 2 (2018): 56.
[69] Raussendorf, Robert, Jim Harrington, and Kovid Goyal. "A fault-tolerant one-way quantum computer." Annals of physics 321.9 (2006): 2242-2270.
[70] Bravyi, Sergey, and Alexei Kitaev. "Universal quantum computation with ideal Clifford gates and noisy ancillas." Physical Review A 71.2 (2005): 022316.
[71] Maslov, Dmitri. "On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization." arXiv preprint arXiv:1508.03273 (2015).
[72] Grassl, Markus, et al. "Applying Grover’s algorithm to AES: quantum resource estimates." Post-Quantum Cryptography. Springer, Cham, 2016.