Is a qubit better than a bit at everything?

In May 2023, a few days into my internship at the Centre for Quantum Technologies, I started reading the standard textbook of quantum information and kept coming back to three questions, which I later wrote into my internship journal. The first asked whether a quantum bit is superior to a classical bit in every aspect. The second asked what the Bell inequality is actually for. The third asked why we need density operators at all. They were beginner’s questions, and I was a beginner: I had just finished my second year of physics at NTU, and I was spending May to July in Marco Tomamichel’s quantum information group, reading about cryptography. This is how I got there, and how that summer answered the first question.

How I got there

My first taste of quantum was QCamp in 2019, a camp the Centre for Quantum Technologies runs for students before university [1]. It was where I first met linear algebra and quantum mechanics, and it was a spark rather than a plan. When I started physics at NTU in 2021, quantum was one interest among several, next to cryptocurrency, which I had been following since 2019.

That changed in 2022 with PH2101 Quantum Mechanics I [2], taught that year by Assoc. Prof. Rainer Dumke and Prof. Christos Panagopoulos. It was simply more fun to me than electrodynamics or photonics, and I wanted to know what it could be used for.

Around the same time I got to know Yanglin Hu, a PhD student in Marco’s group. Through Yanglin I learned what the group works on: quantum information theory, and in particular what quantum mechanics means for cryptography. It was the one place where my two interests met. I found the internship myself rather than through a school placement, and in May 2023 I joined the group as an intern, with Yanglin as my mentor.

Week one: a survey, and the bible

The first thing I read was a survey of quantum homomorphic encryption by Hamlin, Libby and Launchbury [3]. The idea is to hand encrypted quantum data to someone else’s quantum computer, have them compute on it without ever seeing it, and decrypt the answer yourself: privacy against whoever owns the computer. It was exactly the kind of idea I had liked in cryptocurrency, and, as I found out later, the group’s own recent work was on it.

Then came Nielsen and Chuang’s Quantum Computation and Quantum Information [4], the book everyone in the field calls the bible. It was harder than I had expected. The mathematics was a level above anything I had done, and within days I found that my linear algebra and complex numbers were not as solid as I had thought. A senior in the group suggested Riley Perry’s The Temple of Quantum Computing [5], a gentler walk through the same ground, and I read the two side by side: Perry to get the idea, Nielsen and Chuang to get it right. I also went back to working calculations through by hand.

By the end of the second week I had the postulates of quantum mechanics, quantum circuits, superdense coding and teleportation, and a first look at Shannon’s channel capacity. By then I had first answers to all three, and each one mattered for cryptography.

Three questions

First, is a qubit better than a bit at everything? It is not, and the cleanest answer is Holevo’s bound [6]: n qubits can carry at most n bits of classical information, however cleverly they are encoded. A qubit has a continuum of possible states, but a measurement can only ever extract one bit of information from it. Superdense coding sends two bits with one qubit only because the two sides already share an entangled pair [7]. Quantum is not uniformly better. It is different, and cryptography turned out to be where the difference shows most clearly.

Second, why does the Bell inequality matter? Bell showed that any local, classical explanation of two distant measurements can only produce correlations up to a certain strength [8]. Entangled particles go beyond it, as experiments have shown since the 1970s, most famously Aspect’s in 1982 [9], and without loopholes since 2015 [10]. For cryptography this is more than philosophy. Correlations that no local explanation can reproduce cannot have been shared with an eavesdropper in advance, which is the idea behind Ekert’s key distribution protocol [11] and, later, device-independent schemes that do not even trust their own hardware [12].

Third, why density operators? In cryptography one almost never knows the whole state. An eavesdropper holds part of a system, and someone who does not know which of two states was sent holds a mixture of both. The density operator describes what one party can actually see [4], and security statements are statements about it: how close the attacker’s state is to one that knows nothing.

What quantum mechanics gives, and what it takes away

The review papers I read that summer, starting with Broadbent and Schaffner’s survey of quantum cryptography beyond key distribution [13], turned into a map. For each task, whether two people want to keep an eavesdropper out or protect themselves from each other, the question is the same: can quantum mechanics make it secure against any attacker, however much computing power they have?

• Key distributionPossibleBB84, given an authenticated channel [14]
• Bit commitmentImpossibleMayers; Lo and Chau [15] [16]
• Oblivious transferImpossibleLo [17]; buildable from commitment [18]
• Strong coin flippingImpossiblea fair one, that is: one side can always bias it by at least 0.207 [19]
• Weak coin flippingPossiblebias as small as you like [20]
• Homomorphic encryptionWith trade-offsdata privacy, circuit privacy and correctness can’t all be close to perfect at once [21]

The first row is the famous one. Quantum key distribution lets two people agree on a secret key with security that rests on physics rather than on a problem being hard to solve [14]. Scarani and colleagues’ review [22], written partly at CQT, was my guide to how that holds up with real, imperfect devices.

The other rows were the surprise. Tasks that sound simpler than key distribution, such as committing to a bit, turn out to be impossible to make unconditionally secure, quantum or not, and a fair coin flip survives only in a weaker form. For coin flipping I started from Döscher and Keyl’s introduction [23] and Demay and Maurer’s paper on unfair coin tossing [24]. The oblivious transfer row has a twist I liked: with unconditional security, oblivious transfer gives you commitment classically but not the other way round, while in the quantum world commitment gives you oblivious transfer too [18] [13].

The last row was Yanglin’s own work. Earlier, Ouyang, Tan and Fitzsimons had built a homomorphic encryption scheme with information-theoretic security for circuits with a limited number of non-Clifford gates [25]. Yanglin, Yingkai Ouyang and Marco then asked what such schemes must give up [21]. Their key step was a reduction: they showed how to turn a quantum homomorphic encryption scheme into oblivious transfer. Since unconditionally secure oblivious transfer is impossible, perfect homomorphic encryption is impossible too, and the reduction turns that into concrete trade-offs between data privacy, circuit privacy and correctness, even for schemes that only compute Clifford circuits.

My notes from that summer are me working through that chain of reductions, and asking where coin flipping and bit commitment fit into it. That was the answer to my first question. Quantum mechanics gives cryptography something classical physics cannot, and it takes away things we might have hoped for, and some of the sharpest results in the field are proofs of what cannot be done.

Sealing a bit in an envelope

My own project was bit commitment, the building block at the bottom of that chain. A commitment is a digital sealed envelope. Alice puts a bit inside, hands the envelope to Bob, and opens it later. Bob cannot see the bit before she opens it, which is called hiding, and Alice cannot change it after handing it over, which is called binding.

With that one tool, two people who do not trust each other can toss a coin over the phone. Alice commits to a random bit a, Bob announces a random bit b, Alice opens her envelope, and the coin is a ⊕ b. Neither can steer the result: Bob chose b without knowing a, and Alice cannot change a after hearing b. Manuel Blum described this protocol and called it coin flipping by telephone [26].

I implemented a classical commitment scheme, used it to toss coins this way, and worked through how commitment can be built from oblivious transfer. I did not keep that code, so for this post I have rewritten the idea as a short Python script. The envelope itself is a hash of the bit together with a long random number:

import hashlib, secrets

def commit(bit):
    nonce = secrets.token_bytes(32)
    digest = hashlib.sha256(nonce + bytes([bit])).hexdigest()
    return digest, nonce          # send the digest now, keep the nonce to open later

def verify(digest, bit, nonce):
    return hashlib.sha256(nonce + bytes([bit])).hexdigest() == digest

def coin_flip():
    a = secrets.randbits(1)
    digest, nonce = commit(a)         # Alice -> Bob: the envelope
    b = secrets.randbits(1)           # Bob -> Alice: his bit, chosen without seeing a
    assert verify(digest, a, nonce)   # Alice -> Bob: she opens, Bob checks
    return a ^ b

The full script, bit-commitment.py, also builds a commitment out of an ideal oblivious transfer box. Alice commits by acting as the sender n times, offering a random pad and the pad XOR her bit; Bob picks one of each pair without her knowing which. To open to the other bit, Alice would have to flip her pad in exactly the rounds where Bob took the pad XOR bit. She does not know which rounds those are, so in each one she can only guess, and she gets away with it with probability 2⁻ⁿ. One run of the script accepted every honest opening, gave 5,014 heads in 10,000 coin flips, and let the cheater through 0.35% of the time for n = 8, against the 0.39% (2⁻⁸) the theory predicts.

Both of these commitments lean on something. The hash-based one rests on assumptions about SHA-256, and the second needs an oblivious transfer box that someone has to provide. That is unavoidable classically: without a computational assumption or a trusted resource such as an oblivious transfer box, no scheme can be both hiding and binding against a cheater with unlimited computing power. Quantum mechanics was expected to remove the assumption, and in 1997 Mayers, and independently Lo and Chau, proved that it cannot [15] [16]. In any quantum protocol, a committer who keeps the right entangled state can put off her choice until the envelope is opened. So I spent a summer building, classically, a primitive that quantum mechanics has been proven unable to make unconditionally secure, and it was the best way to understand why.

A dinner at Colony

In June the group hosted the Lyon–Singapore Quantum Information Meeting [27], a week of talks at CQT that we called the Merlion Workshop. Most of the talks were beyond me. One on quantum foundations was not beyond my curiosity: it opened up a field I had not known existed, one that tries to settle what quantum mechanics is actually telling us.

The harder part was the dinner. I was an intern among researchers from Lyon and Singapore, and walking up to people I did not know was something I usually avoided. I did it anyway, and they were generous with advice: how to read a paper without drowning in it, how to check that I had really understood it, and which sources to trust. I left that evening less afraid of talking to people than I arrived, and that has mattered more than any single talk.

Explain it to someone else

In July a few PhD students in the group started a study group on quantum cryptography, working from the lecture notes Thomas Vidick and Stephanie Wehner wrote for their quantum cryptography course, which Thomas taught at Caltech and which have since become their book [28]. At the first session, on a Wednesday evening, the organiser paired us up and we took turns explaining topics to each other. It is a humbling test, because it shows very quickly whether you understood a proof or only followed it. Alongside it I read the review papers Yanglin recommended and Mark Wilde’s Quantum Information Theory [29].

What the summer was, honestly

Most of my internship was reading. I did not publish anything, and my reading did not move the group’s research forward. What it changed was how I read. I went in treating papers as things to get through, and came out treating them as arguments to check. I also left with the map above: a sense of what quantum cryptography can and cannot do, and of how much of the field consists of proofs that something is impossible.

Looking back

That summer settled something. Cryptography was where my interest in markets and my interest in quantum met, and I have kept following it since.

So, is a qubit better than a bit at everything? It is not. It can do some things no bit can, and some of the things we hoped it could do turned out to be impossible. That was the most useful thing I learned that summer: in this field, the proofs of what cannot be done matter as much as the protocols.

References

1. Centre for Quantum Technologies, QCamp. qcamp.quantumlah.org ↗
2. Nanyang Technological University, School of Physical and Mathematical Sciences, Physics undergraduate course information: PH2101 Quantum Mechanics I. ntu.edu.sg ↗
3. B. Hamlin, S. Libby and N. Launchbury, Quantum Homomorphic Encryption: A Survey, course project report, CS 410/510 Introduction to Quantum Computing, Portland State University (June 2017). fangsong.info ↗
4. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, Cambridge University Press (2010). Google Books ↗
5. R. T. Perry, The Temple of Quantum Computing, version 1.1 (2006).
6. A. S. Holevo, “Bounds for the quantity of information transmitted by a quantum communication channel,” Problems of Information Transmission 9, 177 (1973).
7. C. H. Bennett and S. J. Wiesner, “Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states,” Physical Review Letters 69, 2881 (1992). doi:10.1103/PhysRevLett.69.2881 ↗
8. J. S. Bell, “On the Einstein Podolsky Rosen paradox,” Physics Physique Fizika 1, 195 (1964). doi:10.1103/PhysicsPhysiqueFizika.1.195 ↗
9. A. Aspect, P. Grangier and G. Roger, “Experimental realization of Einstein-Podolsky-Rosen-Bohm Gedankenexperiment: a new violation of Bell’s inequalities,” Physical Review Letters 49, 91 (1982). doi:10.1103/PhysRevLett.49.91 ↗
10. B. Hensen et al., “Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres,” Nature 526, 682 (2015). doi:10.1038/nature15759 ↗
11. A. K. Ekert, “Quantum cryptography based on Bell’s theorem,” Physical Review Letters 67, 661 (1991). doi:10.1103/PhysRevLett.67.661 ↗
12. A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio and V. Scarani, “Device-independent security of quantum cryptography against collective attacks,” Physical Review Letters 98, 230501 (2007). doi:10.1103/PhysRevLett.98.230501 ↗
13. A. Broadbent and C. Schaffner, “Quantum cryptography beyond quantum key distribution,” Designs, Codes and Cryptography 78, 351 (2016). doi:10.1007/s10623-015-0157-4 ↗
14. C. H. Bennett and G. Brassard, “Quantum cryptography: public key distribution and coin tossing,” in Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, 175 (1984); reprinted in Theoretical Computer Science 560, 7 (2014). doi:10.1016/j.tcs.2014.05.025 ↗
15. D. Mayers, “Unconditionally secure quantum bit commitment is impossible,” Physical Review Letters 78, 3414 (1997). doi:10.1103/PhysRevLett.78.3414 ↗
16. H.-K. Lo and H. F. Chau, “Is quantum bit commitment really possible?,” Physical Review Letters 78, 3410 (1997). doi:10.1103/PhysRevLett.78.3410 ↗
17. H.-K. Lo, “Insecurity of quantum secure computations,” Physical Review A 56, 1154 (1997). doi:10.1103/PhysRevA.56.1154 ↗
18. C. Crépeau, “Quantum oblivious transfer,” Journal of Modern Optics 41, 2445 (1994). doi:10.1080/09500349414552291 ↗
19. A. Chailloux and I. Kerenidis, “Optimal quantum strong coin flipping,” in 50th Annual IEEE Symposium on Foundations of Computer Science, 527 (2009). The lower bound on the bias, about 0.207, is due to A. Kitaev. doi:10.1109/FOCS.2009.71 ↗
20. C. Mochon, “Quantum weak coin flipping with arbitrarily small bias,” (2007). arXiv:0711.4114 ↗
21. Y. Hu, Y. Ouyang and M. Tomamichel, “Privacy and correctness trade-offs for information-theoretically secure quantum homomorphic encryption,” Quantum 7, 976 (2023). doi:10.22331/q-2023-04-13-976 ↗
22. V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus and M. Peev, “The security of practical quantum key distribution,” Reviews of Modern Physics 81, 1301 (2009). doi:10.1103/RevModPhys.81.1301 ↗
23. C. Döscher and M. Keyl, “An introduction to quantum coin tossing,” Fluctuation and Noise Letters 2, R125 (2002). doi:10.1142/S0219477502000944 ↗
24. G. Demay and U. Maurer, “Unfair coin tossing,” in 2013 IEEE International Symposium on Information Theory, 1556 (2013). doi:10.1109/ISIT.2013.6620488 ↗
25. Y. Ouyang, S.-H. Tan and J. F. Fitzsimons, “Quantum homomorphic encryption from quantum codes,” Physical Review A 98, 042334 (2018). doi:10.1103/PhysRevA.98.042334 ↗
26. M. Blum, “Coin flipping by telephone: a protocol for solving impossible problems,” ACM SIGACT News 15(1), 23 (1983). doi:10.1145/1008908.1008911 ↗
27. Lyon–Singapore Quantum Information Meeting, Centre for Quantum Technologies, 5–9 June 2023. Programme ↗
28. T. Vidick and S. Wehner, Introduction to Quantum Cryptography, Cambridge University Press (2023). doi:10.1017/9781009026208 ↗
29. M. M. Wilde, Quantum Information Theory, 2nd edition, Cambridge University Press (2017); the updated text is online as “From classical to quantum Shannon theory”. arXiv:1106.1445 ↗