# Copyright 2018-2021 Xanadu Quantum Technologies Inc.
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
# http://www.apache.org/licenses/LICENSE-2.0
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""
This submodule contains the template for QFT.
"""
import numpy as np
from pennylane import capture, compiler, math
from pennylane.capture import hint
from pennylane.control_flow import for_loop
from pennylane.core.operator import Operator2
from pennylane.decomposition import add_decomps, register_resources
from pennylane.ops import SWAP, ControlledPhaseShift, Hadamard
from pennylane.typing import AbstractWires, Wire
from pennylane.wires import WiresLike
[docs]
class QFT(Operator2):
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
* Gradient recipe: None
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:: python
wires = 3
dev = qp.device('default.qubit',wires=wires)
@qp.qnode(dev)
def circuit_qft(basis_state):
qp.BasisState(basis_state, wires=range(wires))
qp.QFT(wires=range(wires))
return qp.state()
>>> circuit_qft(np.array([1.0, 0.0, 0.0])) # doctest: +SKIP
array([ 0.3536+0.j, -0.3536+0.j, 0.3536+0.j, -0.3536+0.j, 0.3536+0.j,
-0.3536+0.j, 0.3536+0.j, -0.3536+0.j])
.. details::
:title: Available decompositions
.. decomposition-table:: qp.QFT
:symbols: :math:`n` wires
:example: :math:`n=3`
.. decomposition-rule:: _qft_decomposition
:image: /_static/decomposition_thumbnails/qft_cphase_swap.svg
:class:`~.Hadamard` | :math:`n` | 3
:class:`~.ControlledPhaseShift` | :math:`n(n-1)/2` | 3
:class:`~.SWAP` | :math:`\lfloor n/2 \rfloor` | 1
.. details::
:title: Semiclassical Quantum Fourier transform
If the QFT is the last subroutine applied within a circuit, it can be
replaced by a
`semiclassical Fourier transform <https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.76.3228>`_.
It makes use of mid-circuit measurements and dynamic circuit control based
on the measurement values, allowing to reduce the number of two-qubit gates.
As an example, consider the following circuit implementing addition between two
numbers with ``num_wires`` bits (modulo ``2**num_wires``):
.. code-block:: python
dev = qp.device("default.qubit")
@qp.qnode(dev, shots=1)
def qft_add(m, k, num_wires):
m_bin = qp.math.int_to_binary(m, num_wires)
qp.BasisEmbedding(m_bin, wires=range(num_wires))
qp.adjoint(qp.QFT)(wires=range(num_wires))
for j in range(num_wires):
qp.RZ(-k * np.pi / (2**j), wires=j)
qp.QFT(wires=range(num_wires))
return qp.sample()
>>> qft_add(7, 3, num_wires=4)
array([[1, 0, 1, 0]])
The last building block of this circuit is a QFT, so we may replace it by its
semiclassical counterpart:
.. code-block:: python
def scFT(num_wires):
'''semiclassical Fourier transform'''
for w in range(num_wires-1):
qp.Hadamard(w)
mcm = qp.measure(w)
for m in range(w + 1, num_wires):
qp.cond(mcm, qp.PhaseShift)(np.pi / 2 ** (m + 1), wires=m)
qp.Hadamard(num_wires-1)
@qp.qnode(dev)
def scFT_add(m, k, num_wires):
qp.BasisEmbedding(m, wires=range(num_wires))
qp.adjoint(qp.QFT)(wires=range(num_wires))
for j in range(num_wires):
qp.RZ(-k * np.pi / (2**j), wires=j)
scFT(num_wires)
# Revert wire order because of PL's QFT convention
return qp.sample(wires=list(range(num_wires-1, -1, -1)))
>>> qp.set_shots(scFT_add, 1)(7, 3, num_wires=4) # doctest: +SKIP
array([[1, 1, 1, 0]])
"""
arg_specs = {"wires": Wire[-1]}
def __init__(self, wires: WiresLike):
super().__init__(wires)
[docs]
@staticmethod
def compute_matrix(wires: WiresLike): # pylint: disable=arguments-differ
return np.fft.ifft(np.eye(2 ** len(wires)), norm="ortho")
def _qft_decomposition_resources(wires: AbstractWires):
num_wires = len(wires)
return {
Hadamard: num_wires,
SWAP: num_wires // 2,
ControlledPhaseShift: num_wires * (num_wires - 1) // 2,
}
@register_resources(_qft_decomposition_resources)
def _qft_decomposition(wires: WiresLike):
num_wires = len(wires)
shifts = [2 * np.pi * 2**-i for i in range(2, num_wires + 1)]
if compiler.active() or capture.enabled():
shifts = math.array(shifts, like="jax")
wires = math.array(wires, like="jax")
@for_loop(num_wires)
def outer_loop(i):
Hadamard(wires[i])
if num_wires > 1:
@hint({"num-iters": (num_wires - 1) / 2})
@for_loop(num_wires - 1 - i)
def cphaseshift_loop(j):
ControlledPhaseShift(shifts[j], wires=[wires[i + j + 1], wires[i]])
cphaseshift_loop() # pylint: disable=no-value-for-parameter
outer_loop() # pylint: disable=no-value-for-parameter
@for_loop(num_wires // 2)
def swaps(i):
SWAP(wires=[wires[i], wires[num_wires - i - 1]])
swaps() # pylint: disable=no-value-for-parameter
add_decomps(QFT, _qft_decomposition)