|
Quantum state synthesis: relation with decision complexity classes and impossibility of error reduction
(pp754-765)
Hugo Delavenne and François Le Gall
doi:
https://doi.org/10.26421/QIC24.9-10-3
Abstracts:
This work investigates the relationships
between quantum state synthesis complexity classes (a recent concept in
computational complexity that focuses on the complexity of preparing
quantum states) and traditional decision complexity classes. We
especially investigate the role of the
\emph{synthesis
error parameter}, which characterizes the quality of the synthesis in
quantum state synthesis complexity classes.We first show that in the
high synthesis error regime, collapse of synthesis classes implies
collapse of the equivalent decision classes. For more reasonable
synthesis error, we then show a similar relationships for
$\BQP$
and $\QCMA$.
Finally, we show that for quantum state synthesis classes it is in
general impossible to improve the quality of the synthesis: unlike the
completeness and soundness parameters (which can be improved via
repetition), the synthesis error cannot be reduced, even with arbitrary
computational power.
Key Words:
quantum state synthesis,
decision complexity classes, error reduction |
