permutation_reverse_lnn.py

# This code is part of Qiskit.
#
# (C) Copyright IBM 2024
#
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
#
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.
"""
Synthesis of a reverse permutation for LNN connectivity.
"""

from qiskit.circuit import QuantumCircuit


def _append_cx_stage1(qc, n):
    """A single layer of CX gates."""
    for i in range(n // 2):
        qc.cx(2 * i, 2 * i + 1)
    for i in range((n + 1) // 2 - 1):
        qc.cx(2 * i + 2, 2 * i + 1)
    return qc


def _append_cx_stage2(qc, n):
    """A single layer of CX gates."""
    for i in range(n // 2):
        qc.cx(2 * i + 1, 2 * i)
    for i in range((n + 1) // 2 - 1):
        qc.cx(2 * i + 1, 2 * i + 2)
    return qc


def synth_permutation_reverse_lnn_kms(num_qubits: int) -> QuantumCircuit:
    """
    Synthesize reverse permutation for linear nearest-neighbor architectures using
    Kutin, Moulton, Smithline method.

    Synthesis algorithm for reverse permutation from [1], section 5.
    This algorithm synthesizes the reverse permutation on :math:`n` qubits over
    a linear nearest-neighbor architecture using CX gates with depth :math:`2 * n + 2`.

    Args:
        num_qubits: The number of qubits.

    Returns:
        The synthesized quantum circuit.

    References:
        1. Kutin, S., Moulton, D. P., Smithline, L.,
           *Computation at a distance*, Chicago J. Theor. Comput. Sci., vol. 2007, (2007),
           `arXiv:quant-ph/0701194 <https://arxiv.org/abs/quant-ph/0701194>`_
    """

    qc = QuantumCircuit(num_qubits)
    for _ in range((num_qubits + 1) // 2):
        qc = _append_cx_stage1(qc, num_qubits)
        qc = _append_cx_stage2(qc, num_qubits)
    if (num_qubits % 2) == 0:
        qc = _append_cx_stage1(qc, num_qubits)

    return qc