Date: 5th (Mon) of October 2015
Place: University of Tokyo (Hongo Campus), Japan
Invited speakers:
Joseph Fitzsimons (Singapore University of Technology and Design)
Chiara Greganti (University of Vienna)
Matthew McKague (University of Otago)
Daniel Nagaj (Slovak Academy of Sciences)
Dave Touchette (Universite de Montreal)
Program:
9:40-10:20 Joseph Fitzsimons
Title: Blind quantum computing
10:20-11:00 Chiara Greganti
Title: Experimental blind quantum computing
Abstract: I will introduce the essential constituents of photonic experiments as ideal quantum systems for secure quantum computation. After briefly reviewing universal blind quantum computing in a client-server network as well as its application for the verification of quantum computers, I will focus on our recent experiment demonstrating an alternative realization. This measurement-only secure quantum computing experiment shows secure quantum computing and the possibility of verifying the quantum computation by a client that is capable of doing only quantum measurements.
11:00-11:20 Break
11:20-12:00 Matthew McKague
Title: Interactive proofs for BQP via self-tested graph states
Abstract: Using the measurement-based quantum computation model, we construct interactive proofs with non-communicating quantum provers and a classical verifier. Our construction gives interactive proofs for all languages in BQP with a polynomial number of quantum provers, each of which, in the honest case, performs only a single measurement. Our techniques use self-tested graph states. In this regard we introduce two important improvements over previous work. Specifically, we derive new error bounds which scale polynomially with the size of the graph compared with exponential dependence on the size of the graph in previous work. We also extend the self-testing error bounds on measurements to a very general set which includes the adaptive measurements used for measurement-based quantum computation as a special case.
12:00-13:40 Lunch
13:40-14:20 Francois Le Gall
Title: Privacy in Quantum Communication Complexity
Abstract: In two-party quantum communication complexity, Alice and Bob receive some classical inputs and wish to compute some function that depends on both these inputs, while minimizing the communication. This model has found numerous applications in many areas of computer science. One question that has received a lot of attention recently is whether it is possible to perform such protocols in a private way. We show that defining privacy for quantum protocols is not so straightforward and it depends on whether we assume that the registers where Alice and Bob receive their classical inputs are in fact classical registers (and hence unentangled with the rest of the protocol) or quantum registers (and hence can be entangled with the rest of the protocol or the environment). We provide new quantum protocols for the Inner Product function and for Private Information Retrieval, and show that the privacy assuming classical input registers can be exponentially smaller than the privacy assuming quantum input registers. We also argue that the right notion of privacy of a communication protocol is the one assuming classical input registers, since otherwise the players can deviate considerably from the protocol.
14:20-15:00 Dave Touchette
Title: Quantum information complexity
Abstract: For interactive quantum communication, the quantum information complexity of a bipartite task quantifies the least amount of information that must be exchanged between Alice and Bob in any protocol implementing that task. It has an operational interpretation as the amortized quantum communication complexity, that is, the optimal asymptotic communication cost per copy for implementing many copies of the task in parallel.The analogous notion for classical protocols can alternatively be interpreted as the amount of information the protocol transcript leaks about Alice’s input conditional on Bob’s input, plus the amount of information the transcript leaks about Bob’s input conditional on Alice’s input. But for quantum protocols, there is in general no direct analogue to the notion of an overall transcript containing information about the inputs. Perhaps even worse, due to the reversibility of quantum protocols, there exist so-called clean protocols, which only output the correct function value and no further information remains at the end of the protocol about the inputs, apart from each party's respective input and this output. We will discuss how our definition of quantum information complexity avoids these problems, discuss properties of this definition, and argue that to implement many binary functions, even with clean protocols, Alice and Bob must exchange a lot of information during the protocol.
15:00-15:40 Daniel Nagaj
Title: An adaptive attack on Wiesner's quantum money
Abstract: Unlike classical money, which is hard to forge for practical reasons (e.g. producing paper with a certain property), quantum money is attractive because its security might be based on the no-cloning theorem. The first quantum money scheme was introduced by Wiesner circa 1970. Although more sophisticated quantum money schemes were proposed, Wiesner's scheme remained appealing because it is both conceptually clean and relatively easy to implement. We show efficient adaptive attacks on Wiesner's quantum money scheme (and its variant by Bennett et al.), when valid money is accepted and passed on, while invalid money is destroyed. We propose two attacks, the first is inspired by the Elitzur-Vaidman bomb testing problem, while the second is based on the idea of protective measurements. It allows us to break Wiesner's scheme with 4 possible states per qubit, and generalizations which use more than 4 states per qubit. (joint work with Aharon Brodutch, Or Sattath and Dominique Unruh, arXiv:1404.1507)
15:40-16:00 (Short talk) Tomoyuki Morimae (Gunma University)
Title: Verifiable measurement-only blind quantum computing with stabilizer testing
Abstract: We introduce a simple protocol for verifiable measurement-only blind quantum computing. Alice, a client, can perform only single-qubit measurements, whereas Bob, a server, can generate and store entangled many-qubit states. Bob generates copies of a graph state, which is a universal resource state for measurement-based quantum computing, and sends Alice each qubit of them one by one. Alice adaptively measures each qubit according to her program. If Bob is honest, he generates the correct graph state, and therefore Alice can obtain the correct computation result. Regarding the security, whatever Bob does, Bob cannot learn any information about Alice's computation because of the no-signaling principle. Furthermore, evil Bob does not necessarily send the copies of the correct graph state, but Alice can check the correctness of Bob's state by directly verifying stabilizers of some copies. This is the joint work with Masahito Hayashi [M. Hayashi and T. Morimae, arXiv:1505.07535]
16:00-16:20 (Short talk) Yuki Takeuchi (Osaka University)
Title: Blind Quantum Computation over a collective-noise quantum channel
Abstract: Blind quantum computation (BQC) allows a client (Alice), who only possesses relatively poor quantum devices, to delegate universal quantum computation to a server (Bob) in such a way that Bob cannot know Alice’s inputs, algorithm, and outputs. The quantum channel between Alice and Bob is noisy, and the loss over the long distance quantum communication should be also taken into account. Here we propose to use decoherence-free subspace (DFS) to overcome the collective noise in the quantum channel for BQC, which we call DFS-BQC. Our DFS-based protocol allows Alice to faithfully transmit randomly rotated qubits, which are employed in the BFK protocol, with high probability proportional to the single-photon transmission rate of the quantum channel. We combined the ideas based on DFS and the BFK protocol without degrading unconditional security. The proposed DFS-based schemes are generic and hence can be applied for other BQC protocols where Alice sends quantum states to Bob.
Registration:
This workshop is free of charge and open to anyone. No registration is needed.
Venue:
The workshop will be held in Room 007 in the 7th Building of Science of the University of Tokyo (Hongo campus).
Organizer:
Tomoyuki Morimae (Gunma University) Email: [my family name] at gunma-u.ac.jp
Francois Le Gall (University of Tokyo)