Q_is_4_Quantum

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.

ChatGPT suggests (and cites your paper):

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).

Fun read!

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.

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?

except the emission spectra from atoms :)

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.

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!]

It is possible to make quantitative statements that I think capture many of the intuitions you assert. Here was one attempt:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.10...

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).

Time to move to London, will save yourself a fortune :)

Is this known to be true? Its obviously not true for arbitrary irrational numbers

Random question from a very-much-not-computer savvy person on the off chance someone cares to answer: If a tiny charge was levied every time a webserver delivered a page to me would it cure this kind of problem? I'm imagining e.g. my browser has to send some crypto of some variety (or guarantee that it will in the future so as to not slow things down).

>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...

Given access to repeated uses of a coin of unknown bias "p" (which is not 0 or 1) you can (eventually) always generate a new coin flip with bias given (exactly) by:

1. 1/2 (i.e fair - von Neumann)

2. p^2

3. p^2/(p^2+(1-p)^2)

4. sqrt(p)

Number 4 really surprised me, I learned it from this paper: http://www.math.chalmers.se/~wastlund/coinFlip.pdf

But you can never generate the biases:

5. 2p

6. 4p(1-p)

Although... if you change the game to allow a quantum coin then 5. and 6. are possible (a paper of mine: https://arxiv.org/abs/1509.06183)

Perhaps it helps to imagine someone had a "screwy thumb" and the coin only precesses when they "flip" it (in fact people can train themselves to do this, and its very difficult for you, the sucker, to see in the air that the coin is not rotating but just precessing!). Hopefully its obvious that whatever side is initially facing up will be the same one facing up when its caught?

The next step is not at all intuitive to me, namely that even someone trying to do a fair flip causes some precession, and that this isn't decoupled from the rotation.

Unfortunately I don't have a github account, but in case you will take a report from here. In this paper of mine:

https://ar5iv.labs.arxiv.org/html/2303.05514

The references come inline and not well separated from the text (eg in square brackets) like this:

Recently the world was introduced to PYTHEUS Ruiz-Gonzalez et al. (2022); Arlt, Ruiz-Gonzalez, and Krenn (2022). Like his homophonic namesake, PYTHEUS is an explorer, who in just a few short years has already made new scientific discoveriesArlt, Ruiz-Gonzalez, and Krenn (2022)!

I suspect this is related to me using bibtex poorly in the original or something!

Anyway, great work overall, thanks again :)

Its a great start!

It seems to be using the bibtex tags for the inline citations. They don't stand out clearly enough for my liking, and they also have me worried: have I ever used a tag for someones paper like "XXXnonsense" or "dumbassYYY"?? Knowing myself, well....

Perhaps I would quit if things deteriorated to the point I was seriously considered the best option for such!

Presumably talking to the wind here as this thread is old, but nonlocal hidden variables do not break causality! This can be seen explicitly in Bell's trivial model, where the state of a system is just the regular quantum state plus a uniform random number between 0 and 1 (hidden). Or put it this way, if this model "breaks causality" then so does regular non-relativistic quantum theory.

Can't resist mentioning my personal favorite expansion of a sqrt:

sqrt(1-x) = 1- \sum_n C(n)/2^(2n+1) x^(n+1)

where x is in (0,1) and C(n)=binomial(2n,n)/(n+1) is the n'th catalan number.

[Learned this from http://www.math.chalmers.se/~wastlund/coinFlip.pdf]

Great - yet another misaligned incentive to throw into the often stressful mix of how lead authorship should be determined!

Agree with this - the jury is still out on "reality" or otherwise of a wavefunction, and people expend their "real" research efforts differently according to their opinion! Saying "well everything is just mathematics" is a bit like advocating solipsism: people will roll their eyes and stop inviting you to cocktail parties, its a boring position.

Another historical example would be electric and magnetic field lines. My impression is that even Faraday originally had doubts about their reality; others certainly did. They could have just been forever considered a useful mathematical construct. At some point it became clear that thinking of them as really existing, permeating space, and having physical properties akin to those of accepted real stuff (momentum etc) was more useful. Many years after GR was formulated there were arguments about similar mathematical objects (dynamical components of a tensor, or "gravitational waves") should be considered real or not. The story is that Feynman convinced many with a simple thought experiment about how they transmit energy.

There is a fun generalization of the game. Assume the penny has (unknown) bias p. You want to output a new flip with bias some function f(p). So f(p)=1/2 is what you described, ie how to get a fair flip. For some functions it can be even easier, e.g. f(p)=p^2 - definitely only requires two flips.

How about:

f(p)=p^2/(p^2+(1-p)^2)

f(p)=2p(1-p)

f(p)=3p(1-p)

f(p)=sqrt(p)

The last two are tricky, I took them from a paper "functions arising from coin flipping" by Wastlund. (The quantum generalization is even more fun, but this text box is too small to contain it.)

Not OP, and I don't have time (hah) to do the calculation but a rough rule of thumb is that if you take a "normal size" of a quantity (mass, speed, etc) then relativistic effects become measurable when you scale it by c^2, ie about 10^17. So e.g. We have had clocks for a while that are accurate to a part in 10^18, so they can measure time dilation at walking speed. Or detect gravitational time dilation when you lift something (the clock!) up one meter in the earths gravitational field.

Yet another way of saying how amazing this new result is: A second is much "closer" to the age of the universe than it is to a zeptosecond.

Part I (which basically gets you up to the Deutsch-Josza algorithm in quantum computing) is a free pdf on the book's website qisforquantum.org

Thanks for buying! Any money I make eventually works its way back to Malawi where I grew up, so it not going to be squandered :)

A few weeks ago a high school physics teacher who used the book for some extension classes sent me some python code he says will do all of the calculations. I have asked the family friend who maintains the book webpage to put it on there, and I am sure she will when she gets a chance. However if you email me - terry @ qisforquantum.org - it would be great to have someone look at it - I don't know python at all and can't even run it to check it. (I also have some atrocious octave/matlab code of my own which anyone is also welcome to.)

Actually its not quite that simple. The approaches are "equivalent" (in terms of operational/statistical predictions) but not "isomorphic" (even if we restrict the regular linear algebra approach to the same gates as I use in the book). Basically (because of not implementing normalization/unitarity) in certain situations the "mist" retains a count of the number of "Feynman paths" that led to the output state. For example, concatenate two PETE boxes (hadamard gates) and the output is [W,W], concatenate four and its [W,W,W,W]. Operationally identical (you only observe the ball to be certainly white!) and applying a suitable simplification rule you "drop the extras" of course. But if someone (unlike me!) wants to think of these states as having ontological status maybe they would think the distinction is relevant.

A much more interesting example of something similar happens in the Deutch-Hayden version of Heisenberg picture style quantum theory. There from looking at the "state of the world" you can determine which total unitary evolution occurred to get you there. In the Schroedinger picture, if I give you the inital and final states there are many possible unitaries that get you between them. Its possible to go further and come up with versions where not only the total unitary connecting initial and final state is discernable, but also the sequence of Hamiltonian's that implemented it are too.

These things are mainly of interest to people in foundations of course (since they like to play the game of blurring the line between our math and what is "really out there"). I tried to be very careful in the book to maintain the distinction.

Note its not strictly-speaking necessary to learn any linear algebra to "understand" quantum computing, there is a very simple but universal set of string-rewriting rules.

I realise for this audience most people wouldn't get much from it, but I find these rules useful for explaining quantum theory without annoying and fluffy analogies to high school students. You can find the rules in my book _Q is for Quantum_ - Part I which covers quantum computing is a free download on the book website (and the rest will be if I ever get around to producing a corrected pdf, bleh, but if you read part I and don't want to pay for the rest let me know and I'll get it to you...)