story

The following post was adapted from a report I wrote for a reading course. It should be thought of as a starting point for getting started with quantum computation and quantum cryptography. This post isn’t self-contained; think of it as a pointer to some early seminal papers in the field.

If you’re interested in the actual mathematical formalisms common in quantum information theory, “Quantum Computation and Quantum Information” by Nielsen and Chuang is a great resource.

introduction

Encoding information in quantum systems provides an opportunity for the development of novel communication and computing architectures that exploit unitary quantum dynamics. So-called quantum parallelism provides opportunities for speedups over classical computation and the quantum no-cloning theorem allows for the construction of cryptographic protocols that derive security from fundamental physics.

quantum computation

universal quantum computer

It is useful to have a concrete model in mind when talking about quantum computers. Early work by Deutsch [1] extended the Church-Turing hypothesis for classical computers through the proposal of a quantum Turing machine, a simplistic model that captures computational power of any computation that can be performed with quantum unitary dynamics. Deutsch showed that a universal quantum computer could not compute non-recursive functions demonstrating that quantum computers solve the same set of problems as classical computers.

Bernstein and Vazirani [2] later constructed an efficient quantum Turing machine and demonstrated a key relationship between problems that could be solved by a universal quantum computer with high probability in polynomial time, the complexity class known as bounded-error quantum polynomial time (\(BQP\)), and problems solvable by a classical Turing machine (with an oracle for randomness) with high probability in polynomial time, the complexity class known as bounded-error probabilistic polynomial time (\(BPP\), a superset of \(P\)). Formally, they showed that \(P \subseteq BPP\subseteq BQP\), with equality if and only if \(P=PSPACE\); it is commonly believed that this last equality does not hold implying proper containment of \(BPP\)by \(BQP\). Later, Bennett et al. [3] gave evidence that \(NP \not\subseteq BQP\), however this is also not proven. To summarize, it is commonly believed (but not proven) that \(NP \not\subseteq BQP\), but \(P \subsetneq BQP\). This means problems that are provably NP-complete are likely safe from super-polynomial quantum speedup, but classically difficult problems (in \(NP \setminus P\)) could be solved by efficiently by quantum computers – some of these problems are described below.

quantum speedup

Significant classes of classically intractable problems have been shown to be feasible with a universal quantum computer. Algorithms providing exponential speedups have been proposed for problems upon which the security of classical cryptographic primitives are based. Efficient algorithms for The (Abelian) Hidden Subgroup Problem, upon which the security of popular cryptographic protocols including the RSA cryptosystem and Diffie-Hellman key exchange are based [4], have been demonstrated. This has sparked interest in the development of cryptosystems resistant to quantum speedup, so-called post-quantum cryptography [5]. Shor’s algorithm is a polynomial-time quantum for prime factorization and computation of the discrete logarithm [6]. These algorithms are based on finding the period of hidden subgroups and rely on the efficiency of the Quantum Fourier Transform [4]. Significant technical challenges need to be overcome before quantum supremacy can be practically demonstrated; however, the promise of exponential speedup presents a clear challenge to modern cryptographers. The complexity theoretic analysis also does not rule out the possibility of useful polynomial-time speedups of potentially NP-complete problems. Grover [7] proposed a database search algorithm with a quadratic speedup over classical methods. Grover’s algorithm does not require the hidden subgroup structure of Shor’s algorithm, but nonetheless provides significant practical advantage for brute-force attacks on cryptography.

practical quantum computers

There are several proposed models for realizing universal quantum computation: the most popular being the quantum circuit mode and adiabatic quantum computing. Both approaches have been proven to be polynomially equivalent [8]. Maintaining coherence throughout quantum computation is the largest challenge to producing a practical quantum computer: effective quantum error correction is key for any practical computing scheme. Quantum error correction was first proposed by Shor [9]. Gottesman [10] introduced a group-theoretic stabilizer formalism that is commonly used for describing quantum error correcting codes.

quantum cryptography

defining security

The benchmark for security of classical cryptographic protocols is a notion known semantic security often settled for instead of the stronger notion of perfect security, since, while possible, is practically infeasible [11]. The security of quantum cryptosystem is not based on information theoretic grounds but physical ones. The commonly accepted notion of the security of a quantum key distribution protocol, proposed by Mayers [12], is known as unconditional security.

quantum cryptographic primitives

The quantum no-cloning theorem, first described by Wooters and Zurek [13] is the basis for much of quantum cryptography. Early work by Wiesner [14], using the consequence of the no-cloning property, showed the promise of using two-state quantum systems, qubits, for cryptography. Wiesner demonstrated a technique for encoding that would make it highly improbably that attackers could undetectably disturb quantum information encoded in conjugate bases. Bennett and Brassard [15] used this idea to devise the BB84 quantum key exchange protocol and a coin-tossing algorithm. Bennett Brassard’s coin-tossing protocol can be used to implement a cryptographic primitive known as bit commitment, whereby one party wishes to verifiably commit to a choice of bit without revealing information about the committed bit until later. Mayers [16] and independently, Lo and Chau [17] showed that the two key requirements of a quantum bit commitment scheme were incompatible. Namely, no quantum protocol could assure that no information about the committed bit could be gained before the reveal, and the immutability of the committed bit, simultaneously.

references

[1] D. Deutsch, “Quantum theory, the Church-Turing principle and the universal quantum computer,” Proceedings of the Royal Society of London A, pp. 97-117, 1985.

[2] E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1411-1473, 1997.

[3] C. H. Bennett, E. Bernstein, G. Brassard and U. Vazirani, “Strengths and Weaknesses of Quantum Computing,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1510-1523, 1997.

[4] M. Nielsen and I. Chuang, Quantum Computation and Quantum Information, New York: Cambridge University Press, 2010.

[5] D. Stebila, Practical post-quantum key exchange, Cambridge: QCrypt 2017, 2017.

[6] P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer Read More: http://epubs.siam.org/doi/10.1137/S0097539795293172,” SIAM Journal on Computing, vol. 26, no. 5, pp. 1484-1509, 1997.

[7] L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, Philadelphia, 1996.

[8] D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd and O. Regev, “Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation,” SIAM Journal on Computing, vol. 37, no. 1, pp. 166-194, 2007.

[9] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Phys. Rev. A, vol. 52, no. 4, pp. R2493-R2496, 1995.

[10] D. Gottesman, “Stabilizer Codes and Quantum Error Correction,” Pasadena, 1997.

[11] C. E. Shannon, “Communication theory of secrecy systems,” The Bell System Technical Journal, vol. 28, no. 4, pp. 656-715, 1949.

[12] D. Mayers, “Unconditional security in quantum cryptography,” Journal of the ACM, vol. 48, no. 3, pp. 351-406, 2001.

[13] W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned,” Nature, vol. 299, pp. 802-803, 1982.

[14] S. Wiesner, “Conjugate Coding,” ACM SIGACT News, vol. 15, no. 1, pp. 78-88, 1983.

[15] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, vol. 175, p. 8, 1984.

[16] D. Mayers, “The trouble with quantum bit commitment,” 1996.

[17] H.-K. Lo and H. F. Chau, “Is Quantum Bit Commitment Really Possible?,” Phys. Rev. Lett, vol. 78, no. 17, p. 3410, 1997.