Dear quanta,
We have two visitors next week: Or Sattath (July 25-29) and Dominic
Berry (July 25 - Aug 4). Both will be in 6-308.
We will have three events next week also.
1. There will be a group meeting on Wed, July 27 (note the unusual
day) in 6-310.
Visiting student Tianyi Peng will speak.
2. Or Sattath will give a talk Wed at 3pm in room 6C-442.
3. Dominic Berry will give a talk Thurs at 3pm in room 6-310.
Here is more detail on the talks
Or Sattath, Wed, July 27, 3pm, 6C-442
Title: Tokenized signatures from quantum money
Abstract:
The fisherman caught a quantum fish. “Fisherman”, cried the fish, “I
beg you, let me go – and I will grant you three wishes.” The fisherman
agreed. The fish gave the fisherman a quantum computer, three quantum
signing tokens and its classical public key. The fish explained: “use
the tokenized signature scheme on this quantum computer, to sign your
three wishes.”
The fisherman used one of the signing tokens to sign the message “give
me your kingdom and crown, now!” and went to the king’s castle. The
king ran the classical verification algorithm using the fish’s public
key, and since it was valid, the king abide.
The fisherman’s wife wanted to sign ten wishes using their signing
tokens. The fisherman did not want to cheat, and secretly went to meet
the fish once again. “Fish, my wife wants to sign ten wishes.” “Do not
worry, I have learned my lesson from the previous story,” the fish
replied. “The quantum tokens are consumed during the signing. It is
impossible for your polynomial wife to sign even four wishes using the
three signing tokens I have granted you.”
“How does it work?”, wondered the fisherman.“Have you heard of quantum
money? These are quantum states which can be easily verified but are
hard to copy. This tokenized quantum signature extends Aaronson and
Christiano’s quantum money [AC12], which is why the signing tokens
cannot be copied”.
“Does your scheme has more fancy properties?”, asked the fisherman.
“Yes, the scheme has other security guarantees: revocability,
testability and everlasting security. Furthermore, If you’re out at
the sea and your quantum phone only has classical reception, you can
use this scheme to transfer the value of the quantum money to the
shore”, said the fish, and went his way.
--------------------
Dominic Berry, Thurs, July 28, 3pm, 6-310.
Title: Corrections for more accurate Hamiltonian simulation
Abstract: Hamiltonian simulation is a very promising area of quantum
algorithms where quantum computers can provide a dramatic speedup over
classical computers. Until recently, all algorithms had poor scaling
in the allowable error. New algorithms allow for complexity scaling
logarithmically in the allowable error. One is based on implementing
a Taylor series, and another is based on a superposition of different
numbers of steps of a quantum walk. These algorithms are still
somewhat suboptimal because the complexity has a multiplying factor
that is logarithmic in the allowable error, whereas the lower bound
has an additive factor. We have now developed general ways of
correcting these algorithms, eliminating the multiplying factor, and
giving an additive factor that is similar to the lower bound up to
double-logarithmic factors.
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip