On the hardness of distinguishing mixed-state quantum computations
| dc.creator | Rosgen, Bill | |
| dc.creator | Watrous, John | |
| dc.date | 2004-07-22 | |
| dc.date.accessioned | 2026-07-07T03:21:36Z | |
| dc.date.available | 2026-07-07T03:21:36Z | |
| dc.description | This paper considers the following problem. Two mixed-state quantum circuits Q and R are given, and the goal is to determine which of two possibilities holds: (i) Q and R act nearly identically on all possible quantum state inputs, or (ii) there exists some input state that Q and R transform into almost perfectly distinguishable outputs. This problem may be viewed as an abstraction of the following problem: given two physical processes described by sequences of local interactions, are the processes effectively the same or are they different? We prove that this problem is a complete promise problem for the class QIP of problems having quantum interactive proof systems, and is therefore PSPACE-hard. This is in sharp contrast to the fact that the analogous problem for classical (probabilistic) circuits is in AM, and for unitary quantum circuits is in QMA. | |
| dc.description | 17 pages | |
| dc.identifier | https://arxiv.org/abs/cs/0407056 | |
| dc.identifier | http://arxiv.org/abs/cs/0407056 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32260 | |
| dc.subject | Computational Complexity | |
| dc.subject | Quantum Physics | |
| dc.subject | F.1.2; F.1.3 | |
| dc.title | On the hardness of distinguishing mixed-state quantum computations | |
| dc.type | text |