# Source code for pennylane.templates.subroutines.qft

# Copyright 2018-2021 Xanadu Quantum Technologies Inc.

# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at

# Unless required by applicable law or agreed to in writing, software
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
"""
This submodule contains the template for QFT.
"""
# pylint:disable=abstract-method,arguments-differ,protected-access

import functools
import numpy as np

import pennylane as qml
from pennylane.operation import AnyWires, Operation

[docs]class QFT(Operation):
r"""QFT(wires)
Apply a quantum Fourier transform (QFT).

For the :math:N-qubit computational basis state :math:|m\rangle, the QFT performs the
transformation

.. math::

|m\rangle \rightarrow \frac{1}{\sqrt{2^{N}}}\sum_{n=0}^{2^{N} - 1}\omega_{N}^{mn} |n\rangle,

where :math:\omega_{N} = e^{\frac{2 \pi i}{2^{N}}} is the :math:2^{N}-th root of unity.

**Details:**

* Number of wires: Any (the operation can act on any number of wires)
* Number of parameters: 0

Args:
wires (int or Iterable[Number, str]]): the wire(s) the operation acts on

**Example**

The quantum Fourier transform is applied by specifying the corresponding wires:

.. code-block::

wires = 3

dev = qml.device('default.qubit',wires=wires)

@qml.qnode(dev)
def circuit_qft(basis_state):
qml.BasisState(basis_state, wires=range(wires))
qml.QFT(wires=range(wires))
return qml.state()

"""
num_wires = AnyWires

def __init__(self, *params, wires=None, do_queue=True, id=None):
wires = qml.wires.Wires(wires)
self.hyperparameters["n_wires"] = len(wires)
super().__init__(*params, wires=wires, do_queue=do_queue, id=id)

@property
def num_params(self):
return 0

[docs]    @staticmethod
@functools.lru_cache()
def compute_matrix(n_wires):  # pylint: disable=arguments-differ
dimension = 2**n_wires

mat = np.zeros((dimension, dimension), dtype=np.complex128)
omega = np.exp(2 * np.pi * 1j / dimension)

for m in range(dimension):
for n in range(dimension):
mat[m, n] = omega ** (m * n)

return mat / np.sqrt(dimension)

[docs]    @staticmethod
def compute_decomposition(wires, n_wires):  # pylint: disable=arguments-differ,unused-argument
r"""Representation of the operator as a product of other operators (static method).

.. math:: O = O_1 O_2 \dots O_n.

.. seealso:: :meth:~.QFT.decomposition.

Args:
wires (Iterable, Wires): wires that the operator acts on
n_wires (int): number of wires or len(wires)

Returns:
list[Operator]: decomposition of the operator

**Example:**

>>> qml.QFT.compute_decomposition((0,1,2,4))
[Toffoli(wires=[1, 2, 4]), CNOT(wires=[1, 2]), Toffoli(wires=[0, 2, 4])]

"""
shifts = [2 * np.pi * 2**-i for i in range(2, n_wires + 1)]

decomp_ops = []
for i, wire in enumerate(wires):

for shift, control_wire in zip(shifts[: len(shifts) - i], wires[i + 1 :]):
op = qml.ControlledPhaseShift(shift, wires=[control_wire, wire])
decomp_ops.append(op)

first_half_wires = wires[: n_wires // 2]
last_half_wires = wires[-(n_wires // 2) :]

for wire1, wire2 in zip(first_half_wires, reversed(last_half_wires)):
swap = qml.SWAP(wires=[wire1, wire2])
decomp_ops.append(swap)

return decomp_ops


Using PennyLane

Development

API

Internals