LogoQCoder Programming Contest 004
Sign in
← Previous ProblemNext Problem →

C3: Modular Arithmetic II

Time Limit: 3 seconds

Memory Limit: 512 MiB

Score: 300 points

Problem Statement

You are given integers nn, aa and LL.

Implement an oracle OO satisfying the following transition on a quantum circuit qc\mathrm{qc} with 2n+12n + 1 qubits.

For any pair of integers (x,y)(x, y) satisfying 0≤x<L0 \leq x < L and 0≤y<L0 \leq y < L, the oracle satisfies

∣x⟩n∣y⟩n+1→O∣x⟩n∣(y+ax) mod L⟩n+1\ket{x}_{n} \ket{y}_{n+1} \xrightarrow{O} \ket{x}_n \ket{(y + ax)\ \text{mod} \ L}_{n+1}

Constraints

  • 1≤n≤51 \leq n \leq 5
  • 0≤a<L≤2n0 \leq a < L \leq 2^n
  • Global phase is ignored in judge.
  • Integers must be encoded by little-endian.
  • The submitted code must follow the specified format:
from qiskit import QuantumCircuit, QuantumRegister
 
 
def solve(n: int, a: int, L: int) -> QuantumCircuit:
    x, y = QuantumRegister(n), QuantumRegister(n + 1)
    qc = QuantumCircuit(x, y)
    # Write your code here:
 
    return qc

Hints

Open
  • You can consider the way to apply the solution of problem B5.
  • You can consider the following first, for any pair of integers (k,c)(k, c) satisfying 0≤k<L0 \leq k < L and 0≤c≤10 \leq c \leq 1.
∣c⟩1∣k⟩n+1→O∣c⟩1∣(k+ca) mod L⟩n+1\ket{c}_1 \ket{k}_{n+1} \xrightarrow{O} \ket{c}_1 \ket{(k + ca)\ \text{mod} \ L}_{n+1}

Please sign in to submit your answer.

Sign in