This repository has been archived by the owner on Jan 12, 2024. It is now read-only.
The trace simulator uses a non-optimal decomposition of the CCNOT
operation
#1038
Labels
Please describe what you would like the maintenance work to be.
The trace simulator uses the following decomposition for
CCNOT
(CCNOT
==CCX
):qsharp-runtime/src/Simulation/Simulators/QCTraceSimulator/Circuits/CCX.qs
Lines 18 to 23 in e58a90c
qsharp-runtime/src/Simulation/Simulators/QCTraceSimulator/Circuits/CCZ.qs
Lines 19 to 38 in e58a90c
However, this decomposition is naive and far from ideal.
A better decomposition is provided here:
qsharp-runtime/src/Simulation/TargetDefinitions/Decompositions/CCNOTFromCCZ.qs
Lines 22 to 31 in e58a90c
qsharp-runtime/src/Simulation/TargetDefinitions/Decompositions/Utils.qs
Lines 101 to 116 in e58a90c
The above is equivalent to the following circuit:
Indeed, when using the trace simulator with the latter decomposition - the depth is reduced from 15 to 8, and the T-depth is reduced from 5 to 4:
See the complete code here:
https://gist.github.com/jond01/59d6e6732c55d8702479f8c6555e450c
This improvement is remarkable when estimating the resources (depth) required for a large quantum algorithm.
Is there any relevant reason for this inconsistency between the decompositions?
The text was updated successfully, but these errors were encountered: