LogoQCoder Programming Contest 004
Sign in
← Previous ProblemNext Problem →

B2: Controlled Phase Shift

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 200

Writer: PSL

Editorial

Editorial on Hint

Hint: You can consider the following oracle without cc first.

∣k⟩n→Oexp⁡(2πiak2n)∣k⟩n\ket{k}_n \xrightarrow{O} \exp\left(\frac{2\pi i a k}{2^n}\right) \ket{k}_n

First, expand kk in binary representation:

k=k0+2k1+⋯+2n−1kn−1(k0,k1,…,kn−1∈{0,1})k = k_0 + 2k_1 + \cdots + 2^{n-1}k_{n-1} \quad (k_0, k_1, \ldots, k_{n-1} \in \{0, 1\})

Then, the phase change of each computational basis state can be decomposed into each qubit.

exp⁡(2πiak2n)∣k⟩n=exp⁡(2πia(k0+2k1+⋯+2n−1kn−1)2n)∣k0⟩∣k1⟩⋯∣kn−1⟩=exp⁡(2πiak02n)∣k0⟩exp⁡(2πia2k12n)∣k1⟩⋯exp⁡(2πia2n−1kn−12n)∣kn−1⟩\begin{align} \exp\left(\frac{2\pi i a k}{2^n}\right) \ket{k}_n &= \exp\left(\frac{2\pi i a (k_0 + 2k_1 + \cdots + 2^{n-1}k_{n-1})}{2^n}\right) \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \nonumber\\ &= \exp\left(\frac{2\pi i a k_0}{2^n}\right) \ket{k_0} \exp\left(\frac{2\pi i a 2 k_1}{2^n}\right) \ket{k_1} \cdots \exp\left(\frac{2\pi i a 2^{n-1}k_{n-1}}{2^n}\right) \ket{k_{n-1}} \end{align}

Therefore, this oracle can be implemented by applying a phase gate P(θ)P(\theta) with θ=2πa2i/2n\theta = 2\pi a 2^i / 2^n to each qubit.

Editorial on the Problem

As in the hint, the phase change of each computational basis state can be decomposed into each qubit.

exp⁡(2πiakc2n)∣k⟩n∣c⟩1=exp⁡(2πia(k0+2k1+⋯+2n−1kn−1)c2n)∣k0⟩∣k1⟩⋯∣kn−1⟩∣c⟩=exp⁡(2πiak0c2n)∣k0⟩⋯exp⁡(2πia2n−1kn−1c2n)∣kn−1⟩∣c⟩\begin{align} \exp\left(\frac{2\pi i a k c}{2^n}\right) \ket{k}_{n} \ket{c}_1 &= \exp\left(\frac{2\pi i a (k_0 + 2k_1 + \cdots + 2^{n-1}k_{n-1})c}{2^n}\right) \ket{k_0} \ket{k_1} \cdots \ket{k_{n-1}} \ket{c} \nonumber\\ &= \exp\left(\frac{2\pi i a k_0 c}{2^n}\right) \ket{k_0} \cdots \exp\left(\frac{2\pi i a 2^{n-1}k_{n-1} c}{2^n}\right) \ket{k_{n-1}} \ket{c} \end{align}

Since the quantum bit ∣c⟩\ket{c} can be interpreted as a control bit, you can apply controlled phase gates CP(θ)CP(\theta) with θ=2πa2i/2n\theta = 2 \pi a 2^i / 2^n with ∣c⟩\ket{c} as the control bit.

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit
 
 
def solve(n: int, a: int) -> QuantumCircuit:
    qc = QuantumCircuit(n + 1)
 
    for i in range(n):
        theta = 2 * math.pi * a * 2**i / 2**n
        qc.cp(theta, n, i)
 
    return qc