Conversation
Codecov Report❌ Patch coverage is
Additional details and impacted files☔ View full report in Codecov by Sentry. 🚀 New features to boost your workflow:
|
graphix/circ_ext/extraction.py
Outdated
| for edge in combinations(c_set, 2): | ||
| negative_sign ^= edge in og.graph.edges() |
There was a problem hiding this comment.
The following code is a bit simpler and faster if the graph is sparse (but slower if the graph is dense; however, it would be much faster in any case if we used rustworkx!):
| for edge in combinations(c_set, 2): | |
| negative_sign ^= edge in og.graph.edges() | |
| negative_sign ^= graph.subgraph(c_set).number_of_edges() % 2 == 1 |
There was a problem hiding this comment.
Nice, thanks. Done in f99c285. Do you suggest moving to rustworks (adding this to the backlog)?
graphix/circ_ext/compilation.py
Outdated
| """ | ||
| circuit = initialize_circuit(pexp_dag.output_nodes, circuit, copy) # May raise value error | ||
| outputs_mapping = NodeIndex() | ||
| outputs_mapping.extend(pexp_dag.output_nodes) |
There was a problem hiding this comment.
Is there a particular reason for the Pauli strings of pexp_dag to use the pattern numbering instead of the output_nodes numbering? I would prefer Pauli strings to use the output_nodes numbering directly, so that add_pexp can use these indices directly instead of having to take care of outputs_mapping (either by changing the way the Pauli strings are computed, or by remapping them once for all before calling add_to_circuit).
There was a problem hiding this comment.
I'm not sure if I understand this comment.
Pauli strings are defined on output nodes (they are represented as a collection of sets of output nodes + a sign). The mapping outputs_mapping is required because in the current implementation Pauli exponentials (which are just a Pauli string + an angle) don't have information on the order of the output nodes of the original pattern. This information is stored in the parent object, namely, the PauliExponentialDAG. When we compile a Pauli exponential via the ladder pass, we need to iterate over the nodes of the Pauli string in the order defined by the output nodes list.
There was a problem hiding this comment.
I was thinking about something like this: thierry-martinez@d6a1464
The idea is that the mapping of indices can be performed before the compilation so that it separates concerns: the ladder pass (or any other pass implementation) does not have to reimplement the mapping. I'm still not sure whether it would make sense to integrate remap into from_measured_node.
There was a problem hiding this comment.
Sorry, I forgot to update some tests: thierry-martinez@e971fde
There was a problem hiding this comment.
Hi, thanks for the comment. I pushed some mods to your suggestion in 5903cf8.
I agree that it makes sense to manage the node-qubit mapping internally so that potential users don't have to take care about that when writing their compilation passes. However, I think that the object PauliExponentialDAG is a "pure MBQC" construct. It's derived from a pattern, and the nodes remap only makes sense when (and if) we want to synthesise a circuit. Therefore, I think it's best that PauliExponentialDAG.from_focused_flow returns a PauliExponentialDAG defined on output nodes, and that the remapping is done at the level of CompilationPass.er_to_circuit. (This is the mod in my last commit).
By the same logic, it may make sense to remap the Pauli strings in the CliffordMap as well, even if it's not needed for the current implementation of the StimCliffordPass. What do you think?
|
Hi @thierry-martinez, thanks for the review. I addressed all your comments, the corresponding modifications in the stim plugin are in commit matulni/graphix-stim-compiler@843601c. I think it's ready for another round! |
This PR introduces functionality to perform the circuit extraction algorithm presented in Ref. [1] which allows to extract a circuit without ancillas from a strongly deterministic pattern.
Context
The main result of the paper is a procedure to perform the transformation
where$U_{\mathcal{P}}$ is the isometry implemented by the pattern $\mathcal{P}$ (a unitary when the pattern has the same number of inputs and outputs), $C$ is a Clifford map, and $V(\mathbf{\theta})$ is an ordered product of Pauli exponentials.
The structure of the extraction process reads as follows:
flowchart LR n0["Pattern"] n1["OpenGraph"] n2("Focused PauliFlow") subgraph s1["ExtractionResult"] s10("PauliExponentialDAG") s11("CliffordMap") end %% Junction node to merge arrows j1(( )) n3("Graphix circuit") n0 --> n1 n1 --> n2 n2 --> s10 n2 --> s11 %% Merging into the junction s10 --> j1 s11 --> j1 j1 --> n3 %% Styling the junction to be small style j1 fill:#000,stroke-width:0px,width:10pxThe transformation$O(N^3)$ Pauli-flow extraction algorithm in Ref. [2] always returns focused Pauli flows, contrary to the $O(N^5)$ version in Ref. [1] which requires an additional post-processing to focus the correction function.
Pattern->OpenGraph->Focused PauliFlowalready exists in the current implementation of Graphix. TheExtractionResultis the output of the algorithm which is denoted "PdDAG" in [1]. In particular:PauliExponentialDAGis a mapping between measured nodes in the open graph and Pauli exponentials, and a partial order between the measured node (the flow's partial order). Pauli exponentials are a pair of anAngle(the node's measurement angle) and aPauliStringacting on the output nodes of the open graph. The corresponding Pauli string is obtained from the focused flow's correction function.Clifford Mapdescribes a linear transformation between the space of input qubits and the space of output qubits. It is encoded as a map from the Pauli-group generators (The$Z$ -map is also obtained from the focused flow's correction function. The $X$ -map is obtained from the focused flow's correction function of the extended open graph (see Def. C.3 in [1]).
Summary of changes
Added the following to
graphix.flow.core.PauliFlow:is_focused: (method) Verifies if a Pauli flow is focused according to definition 4.3 in Ref. [1].extract_circuit: (method) Returns aExtractionResultobject.pauli_strings: (cached_property) Associates a Pauli string to every corrected node in the flow's correction function.Added new module
graphix.circ_ext.extractionFocused PauliFlow->ExtractionResult.ExtractionResultPauliStringPauliExponentialPauliExponentialDAGCliffordMapAdded new module
graphix.circ_ext.compilationExtractionResult->Graphix circuit.PauliExponentialDAG->Graphix circuitis done with the naive "star" construction (see [3]).CliffordMap->Graphix circuitrelies onstimand currently only supports unitaries (i.e., patterns with the same number of inputa and outputs). To avoid introducing a dependency onstim, theStimCliffordPassis implemented in the external plugingraphix-stim-compiler. This compilation pass together with the tooling introduced in this PR allow to do a round-trip conversion circuit -> MBQC pattern -> circuit.We note that all the transformations in the figure work with parametric objects as well.
References
[1] Simmons, 2021, arXiv:2109.05654.
[2] Mitosek and Backens, 2024, arXiv:2410.23439.
[3] https://quantumcomputing.stackexchange.com/questions/5567/circuit-construction-for-hamiltonian-simulation/11373#11373