Quantum synthesis

Vlasie Catalin Mircea

Hugo Delavenne, François Le Gall

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 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.

Hugo Delavenne, François Le Gall

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.

Mark A. Reed

Mehdi Saeedi, Naser Mohammadzadeh, Mehdi Sedighi +1 more

Existing synthesis-related cost functions are explored and five fundamental properties of an efficient quantum circuit implementation are introduced. In addition, a thorough set of metrics for quantum circuit synthesis are proposed and applied on some well-known synthesis algorithms. Our analysis reveals the requirement of proposing new synthesis algorithms to produce realizable circuits. A new heuristic is also introduced which improves the results of a commonly used synthesis algorithm in terms of the proposed synthesis-related metrics.