| 講演名 | 2019-05-11 量子計算に対する合理的証明 森前 智行(京大), 西村 治道(名大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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. |
| 抄録(英) | 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. |
| キーワード(和) | 量子計算 / 合理的証明 |
| キーワード(英) | quantum computation / rational proof |
| 資料番号 | COMP2019-5 |
| 発行日 | 2019-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2019/5/10(から2日開催) |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) / 瀧本 英二(九州大学) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | ENG-JTITLE |
| タイトル（和） | 量子計算に対する合理的証明 |
| サブタイトル（和） | |
| タイトル（英） | Rational proofs for quantum computing |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 量子計算 / quantum computation |
| キーワード(2)（和/英） | 合理的証明 / rational proof |
| 第 1 著者 氏名（和/英） | 森前 智行 / Tomoyuki Morimae |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 第 2 著者 氏名（和/英） | 西村 治道 / Harumichi Nishimura |
| 第 2 著者 所属（和/英） | 名古屋大学(略称：名大) Nagoya University(略称：Nagoya Univ.) |
| 発表年月日 | 2019-05-11 |
| 資料番号 | COMP2019-5 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-21 |
| ページ範囲 | pp.67-74(COMP), |
| ページ数 | 8 |
| 発行日 | 2019-05-03 (COMP) |