LogoQCoder Programming Contest 005
Sign in
← Previous ProblemNext Problem →

B2: Left Action in Another Fourier Basis

Time Limit: 3 sec

Memory Limit: 512 MiB

Score: 500

Writer: PSL

Editorial

You can gain better insight by splitting E(m,k)E(m, k) based on whether the last n−1n - 1 qubits are in the state ∣0⟩n−1\ket{0}_{n - 1} or not.

First, we decompose E(m,k)E(m, k) as follows:

E(m,k)=12n+1F(m,k)+12nG(m,k)\begin{equation} E(m, k) = \frac{1}{\sqrt{2^{n + 1}}} F(m, k) + \frac{1}{\sqrt{2^n}} G(m, k) \end{equation}

where

F(m,k)=∑0≤a<2∑0≤b<2(−1)am+bk∣a⟩∣b⟩∣0⟩n−1\begin{equation} F(m, k) = \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1} \end{equation} G(m,k)=∑1≤c<2n−1(XmRck⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1\begin{equation} G(m, k) = \sum_{1 \leq c < 2^{n-1}} \left( X^m R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \end{equation}

Next, by using the given hint, we express F(m′,k′)F(m', k') in terms of mleft,kleft,mm_{\text{left}}, k_{\text{left}}, m, and kk as follows:

F(m′,k′)=∑0≤a<2∑0≤b<2(−1)am′+bk′∣a⟩∣b⟩∣0⟩n−1=∑0≤a<2∑0≤b<2(−1)a(mleft+m)+b((−1)mkleft+k)∣a⟩∣b⟩∣0⟩n−1=∑0≤a<2∑0≤b<2(−1)a(mleft+m)+b(kleft+k)∣a⟩∣b⟩∣0⟩n−1=∑0≤a<2∑0≤b<2(−1)amleft+bkleft(−1)am+bk∣a⟩∣b⟩∣0⟩n−1\begin{align} F(m', k') &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am' + bk'} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m_{\text{left}} + m) + b ((-1)^m k_{\text{left}} + k)} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{a (m_{\text{left}} + m) + b (k_{\text{left}} + k)} \ket{a} \ket{b} \ket{0}_{n-1} \\ &= \sum_{0 \leq a < 2} \sum_{0 \leq b < 2} (-1)^{am_{\text{left}} + b k_{\text{left}}} (-1)^{am + bk} \ket{a} \ket{b} \ket{0}_{n-1} \end{align}

Therefore, when the last n−1n - 1 qubits are in the ∣0⟩\ket{0} state, the following two operations are required:

  • If mleft≡1 (mod 2)m_{\text{left}} \equiv 1 \ (\text{mod} \ 2), apply a ZZ gate to ∣a⟩\ket{a}.
  • If kleft≡1 (mod 2)k_{\text{left}} \equiv 1 \ (\text{mod} \ 2), apply a ZZ gate to ∣b⟩\ket{b}.

Similarly, by using the hint, we express G(m′,k′)G(m', k') in terms of mleft,kleft,mm_{\text{left}}, k_{\text{left}}, m, and kk:

G(m′,k′)=∑1≤c<2n−1(Xm′Rck′⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1=∑1≤c<2n−1(Xmleft+mRc((−1)mkleft+k)⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1=∑1≤c<2n−1(Xmleft+mR(−1)mckleft+ck⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1=∑1≤c<2n−1(XmleftRckleftXmRck⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1=∑1≤c<2n−1(XmleftRckleft⊗I1⊗In−1)(XmRck⊗I1⊗In−1)(∣0⟩∣0⟩+∣1⟩∣1⟩)∣c⟩n−1\begin{align} G(m', k') &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m'} R^{ck'} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}} + m} R^{c((-1)^m k_{\text{left}} + k)} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}} + m} R^{(-1)^m ck_{\text{left}} + ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}}} R^{ck_{\text{left}}} X^{m} R^{ck} \otimes I_1 \otimes I_{n-1} \right)(\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ &= \sum_{1 \leq c < 2^{n-1}} \left( X^{m_{\text{left}}} R^{ck_{\text{left}}} \otimes I_1 \otimes I_{n-1} \right) \left( X^{m} R^{ck} \otimes I_1 \otimes I_{n-1} \right) (\ket{0} \ket{0} + \ket{1} \ket{1}) \ket{c}_{n-1} \\ \end{align}

Then, by expanding cc bitwise, the expression XmleftRckleftX^{m_{\text{left}}} R^{ck_{\text{left}}} becomes:

XmleftRckleft=XmleftRc0kleftRc1(2kleft)... Rcn−2(2n−2kleft)\begin{equation} X^{m_{\text{left}}} R^{ck_{\text{left}}} = X^{m_{\text{left}}} R^{c_0 k_{\text{left}}} R^{c_1 (2 k_{\text{left}})} ... \ R^{c_{n-2} (2^{n-2} k_{\text{left}})} \end{equation}

Therefore, when at least one of the last n−1n - 1 qubits is in the ∣1⟩\ket{1} state, the following two operations are required:

  • For any j∈{0,1,…,n−2}j \in \lbrace0, 1, \dots, n-2\rbrace, if cj=1c_{j} = 1, apply the R2jkleftR^{2^j k_{\text{left}}} to ∣a⟩\ket{a}. (You can implement this using the rotation gate RzRz.)
  • If mleft≡1 (mod 2)m_{\text{left}} \equiv 1 \ (\text{mod} \ 2), apply an XX gate to ∣a⟩\ket{a}. (You can implement this using the Problem A3 circuit.)

By performing the above operations in sequence, you can obtain the desired quantum state.

The circuit diagram for n=4,mleft=1n = 4, m_{\text{left}} = 1, and kleft=2k_{\text{left}} = 2 is as follows.

The circuit depth is O(n)O(n).

Sample Code

Below is a sample program:

import math
 
from qiskit import QuantumCircuit, QuantumRegister
from qiskit.circuit.library import XGate, ZGate, RZGate
 
 
def A3(n: int) -> QuantumCircuit:
    m, k = QuantumRegister(1), QuantumRegister(n)
    qc = QuantumCircuit(m, k)
 
    qc.x(m[0])
 
    qc.x(k)
 
    qc.compose(XGate().control(len(k)), [*k, m[0]], inplace=True)
 
    qc.x(k)
 
    return qc
 
 
def solve(n: int, m_left: int, k_left: int) -> QuantumCircuit:
    a, b, c = QuantumRegister(1), QuantumRegister(1), QuantumRegister(n - 1)
    qc = QuantumCircuit(a, b, c)
 
    qc.x(c)
 
    if m_left:
        qc.compose(ZGate().control(len(c)), [*c, a[0]], inplace=True)
    if k_left % 2:
        qc.compose(ZGate().control(len(c)), [*c, b[0]], inplace=True)
 
    qc.x(c)
 
    theta = 2 * math.pi / 2 ** (n - 1)
    for i in range(n - 1):
        angle = theta * k_left * (2 ** i)
        qc.compose(RZGate(angle).control(1),
                   [c[i], a[0]], inplace=True)
 
    if m_left:
        qc.compose(A3(n - 1), [a[0], *c], inplace=True)
 
    return qc