| Presentation | 2019-05-11 Rational proofs for quantum computing Tomoyuki Morimae, Harumichi Nishimura, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | It is an open problem whether a classical client can delegate quantum computing to a remote quantum server in such a way that the correctness of quantum computing is somehow guaranteed. Several protocols for verifiable delegated quantum computing have been proposed, but the client is notcompletely free from any quantum technology: the client has to generate or measure single-qubit states. In this paper, we show that the client can be completely classical if the server is rational (i.e., economically motivated). More precisely, we consider the following protocol. The server first sends the client a message allegedly equal to the solution of the problem that the client wants to solve. The client then gives the server a monetary reward whose amount is calculated in classical probabilistic polynomial-time by using the server's message as an input. The reward function is constructed in such a way that the expectation value of the reward (the expectation over the client's probabilistic computing) is maximum when the server's message is the correct solution to the problem. The rational server who wants to maximize his/her profit therefore has to send the correct solution to the client. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | quantum computation / rational proof |
| Paper # | COMP2019-5 |
| Date of Issue | 2019-05-03 (COMP) |
| Conference Information | |
| Committee | COMP / IPSJ-AL |
|---|---|
| Conference Date | 2019/5/10(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Kumamoto University |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kyoto Univ.) / (Kumamoto Univ) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| Language | ENG-JTITLE |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Rational proofs for quantum computing |
| Sub Title (in English) | |
| Keyword(1) | quantum computation |
| Keyword(2) | rational proof |
| 1st Author's Name | Tomoyuki Morimae |
| 1st Author's Affiliation | Kyoto University(Kyoto Univ.) |
| 2nd Author's Name | Harumichi Nishimura |
| 2nd Author's Affiliation | Nagoya University(Nagoya Univ.) |
| Date | 2019-05-11 |
| Paper # | COMP2019-5 |
| Volume (vol) | vol.119 |
| Number (no) | COMP-21 |
| Page | pp.pp.67-74(COMP), |
| #Pages | 8 |
| Date of Issue | 2019-05-03 (COMP) |