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.
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'm not sure I understand your question. Given that it takes an infinite amount of time to write down the decimal expansion of pi, what might it mean to compute pi in finite time?
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.
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.
This was interesting thanks - makes me wish I had the time to study your examples. But of course I don't, without just turning to an LLM....
If for any of these topics you do manage to get a summary you'd agree with from a (future or better-prompted?) LLM I'd like to read it. Particularly the first and third, the second is somewhat familiar and the fourth was a bit vague.
This proposal requires exponential energy! But you can factorize numbers with only one photon (a tiny amount of energy). Oh yeah, you’ll need an exponential number of modes (you just build a very-low-loss interferometer that does the unitary transformation corresponding to Shor’s algorithm on those modes).
Is finding exponentially inefficient ways of factorizing interesting?
Surely Wofram deserves the Nobel as much as Hopfield and Hinton? Not for this stuff of course (which I doubt many take seriously), but because he also provided us with an amazing computational tool without which physics would be very far behind where it is today?
[And at least I knew his name already unlike our current laureates whom I just had to look up!]
This year is an exception because of the AI Gen AI Artificial Intelligence AI AI zeitgeist.
If we keep giving the physics Nobel to people building computer tools, soon it will have to be renowned physicist Linus Torvalds, whose computational platform underlies every big physics experiment.
I'm not sure physicists would be thrilled if we keep going in that direction.
I think this is one of the rare times I feel comfortable speculating that had he not created Mathematica than someone else would have.
There was a demand and plenty of people with interest.
He was just in the right place with the right set of skills to execute on it before others and won the market in its infancy. Also it's a small enough market that the like of Mircosoft didn't feel the need to come in and crush him like they did Lotus 1-2-3.
I suspect you are right - but multiple Nobel prizes have gone to people who got there only very slightly ahead of others in the race. Would be tough to argue that there are many prizes which are for work that wouldn't have been done within a decade of when the winner actually did do it.
That particular proposal was mathematically wrong for reasons I still find physically perplexing (it turns out that for some events quantum theory allows for stronger memory records - defined via classial mutual information - of entropy decreasing events!). A simple example is in here:
https://arxiv.org/abs/0909.1726
(I am second author).
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.