Actually you can't compose quantum crypto protocols like you can classical ones - the composed protocol needs a new security analysis. Entanglement across protocols often kills the composition!
Interestingly (to me!) it took a while in the 90’s/early 00’s for the community to realise that there are distinct questions:
Question A: Does there exist a set of target states and measurements that implement the task
Question B: Can mistrustful parties find a communication protocol that securely (from their perspective) create/implement those states/measurments.
An example where the answer to A is “no” is fully secure oblivious transfer. There were a bunch of misguided papers trying to find communication protocols for OT, but they were doomed from the start!
An example where the answer to A is “yes" but to B is “no” is strong coin flipping. And an example where the answer to both is “yes” is weak coin flipping. (See Carlos Mochon’s magnus opus arxiv 0711.4114 for the coin flipping examples).
I first articulated the distinction between A and B quant-ph/0202143 but left the proof about OT and Question A as an exercise to the reader! Roger Colbeck in arxiv 0708.2843 provided a simple proof and elucidated the whole situation a lot I think.
Give the humans an order 1,2,3,…, and let a referee read them in that order.
Person k tosses one fair coin and reports H/T.
The referee stops at the first time the reported heads exceed the reported tails.
If N people were consulted, choose one of those N uniformly at random. Output heads iff that chosen person’s coin was heads.
For a one-pass version: instead of storing the whole consulted prefix, the referee can keep a single “currently marked” consulted person, and when the k-th consulted coin arrives, replace the mark by that new person with probability
1/k. When the process stops, the marked person is uniform among the consulted ones.
Yeah sorry, pretty vague, and I'm not sure what the "rules" precisely should be. Roughly I mean something that involves an infinite number of humans but where the workload per human is finite (perhaps only in expectation?) and each human only has to accept and pass on to the next one finite information. [This in the context of calculating pi via the "stupid method" of having each person choose a random integer and then using the probability of co-primeness being 6/pi^2].
My first thought does not achieve the task: expand pi/4 as a sum of positive rational numbers, then have each human use a couple of fair coins from their own Bernoulli factory to output a coin that is heads with probability given by their assigned rational number. The n'th human gets told the partial sum up to that point, flips their bernoulli factory coin and either terminates the protocol if they get heads, otherwise they adds their term to the partial sum they received and passes it on. The problem is the information content in the partial sums will grow with n.
Asher Peres told me that Bill Wootters should be given 99% of the credit for the teleportation discovery (and this is in the context that most of us around at the time presumed the majority of the credit should go to Peres and Wootters who had already been discussing publicly very similar stuff).
I have an extremely vague question; Is there one of these "stupid" ways of computing pi that doesn't involve an infeasible (to humans) infinity? I'm comparing to the "have pick people random integers and the probability they are coprime is 6/pi^2" method, which, again, to really work involves some poor people wasting an infinity of their lives. Your scheme does too from what I understand? Is this necessary?
Off topic: If you search for "quantum bernoulli factory" you will find some work I did that shows f(p)=2p is achievable if your "quantum coins" are presented as coherent superpositions instead of classical incoherent mixtures. Your work on exact sampling completely blew my mind (I'm a physicist!) while I was trying to undersantd that whole field.
>I really wish textbooks with open licenses would take over and they could be reworked and improved year after year by different people
Could anyone explain to me how they think this might work in practice?
I am presently producing an undergrad textbook in quantum theory. I have two motivations: 1. IMO the "qubits first" (ie teach finite-dimensional QM before wave mechanics) approach to introducing the theory is superior (basically only Feynman did it of all the "classic" books) and 2. I'm involved in third world education and I want the book to be freely downloadable.
Now its a lot of work despite having taught the course multiple times and produced comprehensive lecture notes etc. Once its done I am sure I will not have the time to keep updating it, expanding on the problem sets and so on. A former student on the course is helping with the conversion and he will be a co-author, but like me he sees it as a service not at all about producing a product. So I think we're both very open to the idea of such "open license".
Given all that here are the kinds of questions that immediately arise:
- Mechanically how should one make the book available for such re-working? Put the source files on github? (Not something I've ever used, but I know roughly how it works).
- Via what mechanism does someone get to be credited for work they might do on better versions?
- Who decides what is the current "definitive" or "best" version? I will have a separate website for the book so I guess new versions can be announced there. But one way or the other I won't be involved forever.
- QM is fraught with crackpots, people who have whacky ideas on how to explain things and so on. Can they be prevented from "taking over", rewriting large chunks into (what I would view as) nonsense and so on? Note that presumably my name would still be associated with the new versions, so the issue is primarily not lending credence to stuff I fundamentally disagree with, not that they shouldn't be allowed to go do their thing.
- We will make a POD service available for purchasing hardcopies, the (expected to be small) royalties from which would be donated to third world physics/math education. Is there some license that can ensure any subsequent use of the material is also similarly non-profit?
I can see some (though not perfect) analogies with open-source software, so perhaps someone here has useful ideas about this kind of thing already...
Interestingly (to me!) it took a while in the 90’s/early 00’s for the community to realise that there are distinct questions:
Question A: Does there exist a set of target states and measurements that implement the task
Question B: Can mistrustful parties find a communication protocol that securely (from their perspective) create/implement those states/measurments.
An example where the answer to A is “no” is fully secure oblivious transfer. There were a bunch of misguided papers trying to find communication protocols for OT, but they were doomed from the start!
An example where the answer to A is “yes" but to B is “no” is strong coin flipping. And an example where the answer to both is “yes” is weak coin flipping. (See Carlos Mochon’s magnus opus arxiv 0711.4114 for the coin flipping examples).
I first articulated the distinction between A and B quant-ph/0202143 but left the proof about OT and Question A as an exercise to the reader! Roger Colbeck in arxiv 0708.2843 provided a simple proof and elucidated the whole situation a lot I think.