講演抄録/キーワード |
講演名 |
2023-05-29 16:30
[ポスター講演]A parallel, branch and bound algorithm for a combinatorial instance of quantum hypothesis testing ○Baasanchimed Avirmed・Kaito Niinomi・Michele Dall'Arno(Toyohashi U. of Technology) |
抄録 |
(和) |
[学生発表賞希望, application for student presentation award] We consider a particular instance of the quantum hypothesis testing problem, known as quantum guesswork, in which the guessing party receives an unknown state from a quantum ensemble and is allowed to query one state at a time. It has recently been shown that such an operational setup is equivalent to a particular instance of a combinatorial problem known as quadratic assignment problem, which is known to be NP-hard in general. Here, we exploit such a combinatorial reformulation of the quantum guesswork to devise and implement in the C programming language a parallel, branch and bound algorithm for the exact computation of the guesswork of any given qubit ensemble. While problem sizes above twenty are typically considered challenging for general quadratic assignment instances, our algorithm solves instances of size thirty in hours. In particular, we report on the exact expression of the guesswork for a broad class of symmetric ensembles. |
(英) |
[学生発表賞希望, application for student presentation award] We consider a particular instance of the quantum hypothesis testing problem, known as quantum guesswork, in which the guessing party receives an unknown state from a quantum ensemble and is allowed to query one state at a time. It has recently been shown that such an operational setup is equivalent to a particular instance of a combinatorial problem known as quadratic assignment problem, which is known to be NP-hard in general. Here, we exploit such a combinatorial reformulation of the quantum guesswork to devise and implement in the C programming language a parallel, branch and bound algorithm for the exact computation of the guesswork of any given qubit ensemble. While problem sizes above twenty are typically considered challenging for general quadratic assignment instances, our algorithm solves instances of size thirty in hours. In particular, we report on the exact expression of the guesswork for a broad class of symmetric ensembles. |
キーワード |
(和) |
quantum guesswork / quantum ensemble / quantum hypothesis testing / quantum state distrimination / quadratic assignment problem / / / |
(英) |
quantum guesswork / quantum ensemble / quantum hypothesis testing / quantum state distrimination / quadratic assignment problem / / / |
文献情報 |
信学技報 |
資料番号 |
|
発行日 |
|
ISSN |
|
PDFダウンロード |
|
|