cqlib_core/compile/transform/
virtual_permutation.rs

1// This code is part of Cqlib.
2//
3// (C) Copyright China Telecom Quantum Group 2026
4//
5// This code is licensed under the Apache License, Version 2.0.
6// You may obtain a copy of this license in the LICENSE.txt file in
7// the root directory of this source tree or at
8// http://www.apache.org/licenses/LICENSE-2.0.
9//
10// Any modifications or derivative works of this code must retain this
11// copyright notice, and modified files need to carry a notice indicating
12// that they have been altered from the originals.
13
14//! Pre-layout elimination of logical wire permutations.
15//!
16//! A logical SWAP does not need to become a physical operation when layout is
17//! still free to choose where logical outputs reside. This transform removes
18//! eligible SWAP operations, redirects every later operation to the wire that
19//! carries the corresponding logical state, and returns an explicit output
20//! permutation for composition with routing metadata.
21//!
22//! The direction of [`VirtualPermutation`] is part of the API contract:
23//!
24//! ```text
25//! original logical output -> rewritten circuit output wire
26//! ```
27//!
28//! If routing later reports a layout from rewritten outputs to physical
29//! qubits, [`VirtualPermutation::compose_final_layout`] produces the complete
30//! original-output-to-physical mapping.
31
32use crate::circuit::{Circuit, Instruction, Operation, Qubit, StandardGate, ValueOperation};
33use crate::compile::CompilerError;
34use crate::compile::transform::CircuitAnalysis;
35use crate::compile::transform::rebuild::CircuitRebuildContext;
36use crate::device::{Layout, LogicalQubit, PhysicalQubit};
37use std::collections::BTreeMap;
38
39/// Output-wire permutation accumulated while logical SWAPs are removed.
40///
41/// Each entry maps an output qubit in the original circuit to the output wire
42/// carrying that state in the rewritten circuit. Inputs remain identity-mapped;
43/// this permutation affects output interpretation only.
44#[derive(Debug, Clone, Default, PartialEq, Eq)]
45pub struct VirtualPermutation {
46    original_output_to_rewritten_output: BTreeMap<LogicalQubit, LogicalQubit>,
47}
48
49impl VirtualPermutation {
50    /// Creates the identity output permutation for `qubits`.
51    pub fn identity(qubits: impl IntoIterator<Item = Qubit>) -> Self {
52        Self {
53            original_output_to_rewritten_output: qubits
54                .into_iter()
55                .map(|qubit| {
56                    let logical = LogicalQubit::from_qubit(qubit);
57                    (logical, logical)
58                })
59                .collect(),
60        }
61    }
62
63    /// Returns the rewritten output wire carrying `original_output`.
64    pub fn rewritten_output(&self, original_output: LogicalQubit) -> Option<LogicalQubit> {
65        self.original_output_to_rewritten_output
66            .get(&original_output)
67            .copied()
68    }
69
70    /// Returns the complete original-output-to-rewritten-output mapping.
71    pub fn original_output_to_rewritten_output(&self) -> &BTreeMap<LogicalQubit, LogicalQubit> {
72        &self.original_output_to_rewritten_output
73    }
74
75    /// Returns whether this output permutation is the identity.
76    pub fn is_identity(&self) -> bool {
77        self.original_output_to_rewritten_output
78            .iter()
79            .all(|(original, rewritten)| original == rewritten)
80    }
81
82    /// Composes this output permutation with a routed final layout.
83    ///
84    /// `rewritten_final_layout` maps rewritten circuit outputs to physical
85    /// qubits. The returned layout maps original circuit outputs to those same
86    /// physical qubits:
87    ///
88    /// ```text
89    /// final(original) = rewritten_final_layout(permutation(original))
90    /// ```
91    ///
92    /// # Errors
93    ///
94    /// Returns [`CompilerError::InvalidInput`] when the supplied layout does
95    /// not map every rewritten output represented by this permutation.
96    pub fn compose_final_layout(
97        &self,
98        rewritten_final_layout: &Layout,
99    ) -> Result<Layout, CompilerError> {
100        let mut mapping = BTreeMap::new();
101        for (original, rewritten) in &self.original_output_to_rewritten_output {
102            let physical = rewritten_final_layout
103                .get_physical(*rewritten)
104                .ok_or_else(|| {
105                    CompilerError::InvalidInput(format!(
106                        "final layout does not map rewritten output {rewritten} required by virtual permutation"
107                    ))
108                })?;
109            mapping.insert(*original, physical);
110        }
111
112        Layout::new(
113            self.original_output_to_rewritten_output
114                .keys()
115                .copied()
116                .collect(),
117            rewritten_final_layout
118                .physical_qubits()
119                .collect::<Vec<PhysicalQubit>>(),
120            Some(mapping),
121        )
122        .map_err(|error| {
123            CompilerError::InvariantViolation(format!(
124                "failed to compose virtual permutation with final layout: {error}"
125            ))
126        })
127    }
128
129    fn swap_outputs(
130        &mut self,
131        left: LogicalQubit,
132        right: LogicalQubit,
133    ) -> Result<(), CompilerError> {
134        let left_output = self.rewritten_output(left).ok_or_else(|| {
135            CompilerError::InvariantViolation(format!(
136                "virtual permutation does not contain logical qubit {left}"
137            ))
138        })?;
139        let right_output = self.rewritten_output(right).ok_or_else(|| {
140            CompilerError::InvariantViolation(format!(
141                "virtual permutation does not contain logical qubit {right}"
142            ))
143        })?;
144        self.original_output_to_rewritten_output
145            .insert(left, right_output);
146        self.original_output_to_rewritten_output
147            .insert(right, left_output);
148        Ok(())
149    }
150}
151
152/// Coarse disposition of a virtual-permutation elimination attempt.
153#[derive(Debug, Clone, Copy, PartialEq, Eq)]
154pub enum VirtualPermutationElisionStatus {
155    /// No eligible logical permutation was present.
156    Unchanged,
157    /// At least one logical SWAP was removed.
158    Changed,
159    /// Structured control flow made a single static output permutation unsafe.
160    SkippedControlFlow,
161}
162
163/// Result of [`elide_virtual_permutations`].
164#[derive(Debug, Clone, PartialEq)]
165pub struct VirtualPermutationElisionResult {
166    changed_circuit: Option<Circuit>,
167    virtual_permutation: VirtualPermutation,
168    elided_swap_count: usize,
169    status: VirtualPermutationElisionStatus,
170}
171
172impl VirtualPermutationElisionResult {
173    /// Returns the rewritten circuit when the transform changed the input.
174    pub fn changed_circuit(&self) -> Option<&Circuit> {
175        self.changed_circuit.as_ref()
176    }
177
178    /// Consumes the result and returns the rewritten circuit when changed.
179    pub fn into_changed_circuit(self) -> Option<Circuit> {
180        self.changed_circuit
181    }
182
183    /// Returns the original-output-to-rewritten-output permutation.
184    pub fn virtual_permutation(&self) -> &VirtualPermutation {
185        &self.virtual_permutation
186    }
187
188    /// Returns the number of SWAP operations represented by the permutation.
189    pub fn elided_swap_count(&self) -> usize {
190        self.elided_swap_count
191    }
192
193    /// Returns the transform disposition.
194    pub fn status(&self) -> VirtualPermutationElisionStatus {
195        self.status
196    }
197}
198
199/// Removes eligible top-level logical SWAPs and returns their output mapping.
200///
201/// An eligible SWAP is an unlabeled, parameter-free standard SWAP. Labeled
202/// SWAPs are preserved because removing them would discard operation metadata.
203/// All other operations, including measurements, resets, barriers, symbolic
204/// gates, and runtime classical data operations, are preserved with their
205/// qubits redirected through the current permutation. Classical handles,
206/// measurement bit order, operation labels, and global phase are preserved by
207/// the shared rebuild infrastructure.
208///
209/// Circuits containing structured classical control are conservatively left
210/// unchanged. Branches and loops can have path-dependent output permutations,
211/// which cannot be represented by this result's single static mapping.
212pub fn elide_virtual_permutations(
213    circuit: &Circuit,
214) -> Result<VirtualPermutationElisionResult, CompilerError> {
215    let mut virtual_permutation = VirtualPermutation::identity(circuit.qubits());
216    if CircuitAnalysis::analyze(circuit).has_classical_control {
217        return Ok(VirtualPermutationElisionResult {
218            changed_circuit: None,
219            virtual_permutation,
220            elided_swap_count: 0,
221            status: VirtualPermutationElisionStatus::SkippedControlFlow,
222        });
223    }
224
225    if !circuit.operations().iter().any(is_elidable_swap) {
226        return Ok(VirtualPermutationElisionResult {
227            changed_circuit: None,
228            virtual_permutation,
229            elided_swap_count: 0,
230            status: VirtualPermutationElisionStatus::Unchanged,
231        });
232    }
233
234    let rebuild = CircuitRebuildContext::new(circuit);
235    let mut rewritten = Vec::<ValueOperation>::with_capacity(circuit.operations().len());
236    let mut elided_swap_count = 0usize;
237
238    for operation in circuit.operations() {
239        if is_elidable_swap(operation) {
240            let [left, right] = operation.qubits.as_slice() else {
241                return Err(CompilerError::InvariantViolation(
242                    "standard SWAP must have exactly two qubits".to_string(),
243                ));
244            };
245            virtual_permutation.swap_outputs(
246                LogicalQubit::from_qubit(*left),
247                LogicalQubit::from_qubit(*right),
248            )?;
249            elided_swap_count += 1;
250            continue;
251        }
252
253        let mut preserved =
254            rebuild.remap_preserved_operation(circuit, operation, rebuild.root_classical())?;
255        for qubit in &mut preserved.qubits {
256            *qubit = virtual_permutation
257                .rewritten_output(LogicalQubit::from_qubit(*qubit))
258                .ok_or_else(|| {
259                    CompilerError::InvariantViolation(format!(
260                        "operation references qubit {qubit} absent from virtual permutation"
261                    ))
262                })?
263                .qubit();
264        }
265        rewritten.push(preserved);
266    }
267
268    let rewritten = rebuild.finish(circuit.qubits(), rewritten, circuit.global_phase())?;
269    Ok(VirtualPermutationElisionResult {
270        changed_circuit: Some(rewritten),
271        virtual_permutation,
272        elided_swap_count,
273        status: VirtualPermutationElisionStatus::Changed,
274    })
275}
276
277fn is_elidable_swap(operation: &Operation) -> bool {
278    matches!(
279        operation.instruction,
280        Instruction::Standard(StandardGate::SWAP)
281    ) && operation.qubits.len() == 2
282        && operation.params.is_empty()
283        && operation.label.is_none()
284}
285
286#[cfg(test)]
287#[path = "./virtual_permutation_test.rs"]
288mod virtual_permutation_test;
cqlib_core/compile/transform/virtual_permutation.rs

cqlib_core/compile/transform/
virtual_permutation.rs
