Rapid solution of problems by quantum computation. (English) Zbl 0792.68058
Summary: A class of problems is described which can be solved more efficiently by quantum computation than by any classical or stochastic method. The quantum computation solves the problem with certainty in exponentially less time than any classical deterministic computation.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |
References:
| [1] | Deutsch D, Jozsa R. Rapid solution of problems by quantum computation. Math Phys Sci, 1992, 439: 553-558 · Zbl 0792.68058 |
| [2] | Bernstein E, Vazirani U. Quantum complexity theory. SIAM J Comput, 1997, 26: 1411-1473 · Zbl 0895.68042 |
| [3] | Simon D R. On the power of quantum computation. SIAM J Comput, 1997, 26: 1474-1483 · Zbl 0883.03024 |
| [4] | Grover L K. Quantum mechanics helps in searching for a needle in haystack. Phys Rev Lett, 1997, 79: 325-328 |
| [5] | Shor P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput, 1997, 26: 1484-1509 · Zbl 1005.11065 |
| [6] | Mosca M, Ekert A. The hidden subgroup problem and eigenvalue estimation on a quantum computer. In: Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communication. Berlin: Springer, 1999 · Zbl 0945.68064 |
| [7] | Hallgren S, Russell A, Ta-Shma A. The hidden subgroup problem and quantum computation using group representations. SIAM J Comput, 2003, 32: 916-934 · Zbl 1029.81015 |
| [8] | Bennett C H, Brassard G. Quantum cryptography:public key distribution and coin tossing. In: Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalor, 1984. 10-12 |
| [9] | Bennett C H, Brassard G, Crépeau C, et al. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys Rev Lett, 1993, 70: 1895-1899 · Zbl 1051.81505 |
| [10] | Bennett C H, DiVincenzo D P, Smolin J A, et al. Mixed-state entanglement and quantum error correction. Phys Rev A, 1996, 54: 3824-3851 · Zbl 1371.81041 |
| [11] | Leung D W. Quantum vernam cipher. Quantum Inf Comput, 2002, 2: 14-34 · Zbl 1187.81089 |
| [12] | Shi J J, Shi R H, Guo Y, et al. Batch proxy quantum blind signature scheme. Sci China Inf Sci, 2013, 56: 052115 · Zbl 1488.94094 |
| [13] | Xiao F Y, Chen H W. Construction of minimal trellises for quantum stabilizer codes. Sci China Inf Sci, 2013, 56: 012306 · Zbl 1488.81013 |
| [14] | Gehani A, Labean T H, Reif J H. DNA-based cryptography. In: Proceedings of the 5th Annual Meeting on DNA Based Computers, Cambridge, 2003. 233-249 · Zbl 0970.68055 |
| [15] | Lu M X, Lai X J, Xiao G Z, et al. A symmetric key cryptography with DNA technology. Sci China Ser F-Inf Sci, 2007, 50: 324-333 · Zbl 1142.94012 |
| [16] | Lai X J, Lu M X, Qin L, et al. Asymmetric encryption and signature method with DNA technology. Sci China Inf Sci, 2010, 53: 506-514 · Zbl 1497.94100 |
| [17] | Okamoto T, Tanaka K, Uchiyama S. Quantum public-key cryptosystems. In: Proceedings of 20th Annual International Cryptology Conference, Santa Barbara, 2000. 147-165 · Zbl 0995.94535 |
| [18] | Bernstein D J, Buchmann J, Dahmen E. Post-quantum Cryptography. Berlin: Springer, 2000 |
| [19] | Wang H Z, Zhang H G, Wang Z Y, et al. Extended multivariate public key cryptosystems with secure encryption function. Sci China Inf Sci, 2011, 54: 1161-1171 · Zbl 1237.94116 |
| [20] | Mu L W, Liu X C, Liang C L. Improved construction of LDPC convolutional codes with semi-random parity-check matrices. Sci China Inf Sci, 2014, 57: 022304 · Zbl 1357.94086 |
| [21] | Biham E, Shamir A. Differential cryptanalysis of DES-like cryptosystems. J Cryptol, 1991, 4: 3-72 · Zbl 0729.68017 |
| [22] | Biham E, Shamir A. Differential cryptanalysis of the full 16-round DES. In: Proceedings of the 12th Annual International Cryptology Conference, Santa Barbara, 1993. 487-496 · Zbl 0809.94017 |
| [23] | Feng D G. Cryptanalysis (in Chinese). Beijing: Tsinghua University Press, 2000 |
| [24] | Bennett C H, Brassard G, Vazirani U, et al. Strengths and weaknesses of quantum computing. SIAM J Comput, 1997, 26: 1510-1523 · Zbl 0895.68044 |
| [25] | Sleator T, Weinfurter H. Realizable universal quantum logic gates. Phys Rev Lett, 1995, 74: 4087-4090 · Zbl 1020.81552 |
| [26] | Barenco A, Deutsch D, Ekert A, et al. Conditional quantum dynamics and logic gates. Phys Rev Lett, 1995, 74: 4083-4086 |
| [27] | Monroe C, Meekhof D M, King B E, et al. Demonstration of a fundamental quantum logic gate. Phys Rev Lett, 1995, 75: 4714-4717 · Zbl 1020.81550 |
| [28] | Vedral V V, Barenco A, Ekert A. Quantum networks for elementary arithmetic operations. Phys Rev A, 1996, 54: 147-153 |
| [29] | Beckman D, Chari A N, Devabhaktuni S, et al. Efficient networks for quantum factoring. Phys Rev A, 1996, 54: 1034-1063 |
| [30] | Christof Z. Fast versions of Shor’s quantum factoring algorithm. arXiv: quant-ph/9806084 |
| [31] | Parker S, Plenio M B. Efficient factorization with a single pure qubit and logN mixed qubits. Phys Rev Lett, 2000, 85: 3049-3052 |
| [32] | Susan L. Protecting Information: from Classical Error Correction to Quantum Cryptograph. Cambridge: Cambridge University Press, 2006 · Zbl 1210.81001 |
| [33] | de Riedmatten H, Afzelius M, Staudt M U, et al. A solid-state light-matter interface at the single-photon level. Nature, 2008, 456: 773-777 |
| [34] | Mariantoni M, Wang H, Yamamoto T, et al. Implementing the quantum von Neumann architecture with superconducting circuits. Science, 2011, 334: 61-65 |
| [35] | Kashefi E, Kent A, Vedral V, et al. Comparison of quantum oracles. Phys Rev A, 2002, 65: 050304 |
| [36] | Nielsen M A, Chuang I L. Quantum Computation and Quantum Information. Cambridge: Cambridge University Press, 2010 · Zbl 1288.81001 |
| [37] | Hastad J. Tensor rank is NP-complete. J Algorithms, 1990, 11: 644-654 · Zbl 0716.65043 |
| [38] | Hillar C J, Lim L-H. Most tensor problems are NP hard. J ACM, 2013, 60: 45 · Zbl 1281.68126 |
| [39] | Mao S, Zhang H G, Wu W Q, et al. A resistant quantum key exchange protocol and its corresponding encryption scheme. China Commun, 2014, 11: 124-134 |
| [40] | Schneier B. Applied Cryptography: Protocols, Algorithms, and Source Code in C. New York: Wiley, 1996 · Zbl 0853.94001 |
| [41] | Wu W Q, Zhang H G, Mao S W, et al. Quantum algorithm to find invariant linear structure of MD hash functions. Quantum Inf Process, 2015, 14: 813-829 · Zbl 1311.81089 |
| [42] | Wu W Q, |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
