B2: The Hidden Polynomial I

Problem Statement

Story

We are the QCoder Order, worshippers of quantum programming. We have a hidden polynomial, $f(x)$, that has been protected for centuries. The polynomial $f(x)$ is defined using an $n$-bit odd integer $A$ and an $n$-bit integer $B$ as follows:

Recently, we performed a sacred ritual to transfer this polynomial to an oracle $O$. If the ritual was successful, the oracle $O$ should behave as follows:

Here, $\oplus$ denotes the bitwise XOR operator, and $(f(x)\bmod 2^n)$ denotes the remainder when $f(x)$ is divided by $2^n$.

Unfortunately, because the ritual's procedure is extremely complicated, no one knows if the oracle was generated correctly. We know that if the ritual failed, the coefficient $A$ would be recorded as $0$.

Your mission is to determine whether the ritual succeeded—i.e., whether the oracle $O$ has been implemented correctly.

Note that the polynomial $f(x)$ is our top secret. To protect the details of $f(x)$, you can only call the oracle $1$ time.

Detailed Description

Given an integer $n$, you may implement any operations you like on a $2n$-qubit quantum circuit $\mathrm{qc}_{\mathrm{before}}$, and on a quantum circuit $\mathrm{qc}_{\mathrm{after}}$ that has $2n$ qubits and $1$ classical register.

Implement operations on these quantum circuits that satisfy the following requirement.

The given oracle $O$ is either $O_1$ or $O_0$. For any pair of integers $(x,y)$ satisfying $0 \leq x < 2^n$ and $0 \leq y < 2^n$, the required transformation is as follows:

When $\mathrm{qc}_{\mathrm{before}},\,O,\,\mathrm{qc}_{\mathrm{after}}$ are applied in this order to the zero state $\ket{0}$, the measurement result written to the classical register must be $1$ if $O=O_1$, and $0$ if $O=O_0$.

Constraints

• $n > 2$
• $0 \leq A, B < 2^n$
• $A$ is odd.
• Integers must be encoded by little-endian.
• Global phase is ignored in judge.
• The submitted code must follow the specified format:
  • before_oracle(n: int) -> QuantumCircuit: the quantum circuit $\mathrm{qc}_{\mathrm{before}}$ before calling the oracle.
  • after_oracle(n: int) -> QuantumCircuit: the quantum circuit $\mathrm{qc}_{\mathrm{after}}$ after calling the oracle. You must write the measurement result to the classical register c in this quantum circuit.

from qiskit import ClassicalRegister, QuantumCircuit, QuantumRegister
 
"""
You can apply measurement as follows
         (e.g., when measuring x[0]):
qc.measure(x[0], c[0])
"""
 
 
def before_oracle(n: int) -> QuantumCircuit:
    x = QuantumRegister(n)
    y = QuantumRegister(n)
    qc = QuantumCircuit(x, y)
 
    # Write your code here:
 
    return qc
 
 
def after_oracle(n: int) -> QuantumCircuit:
    x = QuantumRegister(n)
    y = QuantumRegister(n)
    c = ClassicalRegister(1)
    qc = QuantumCircuit(x, y, c)
 
    # Write your code here:
 
    return qc

In the judge, the functions are called in the following order:

1. before_oracle(n)
2. (the oracle $O$)
3. after_oracle(n)

After that, the judge concludes that “the ritual succeeded” if $c = 1$, and that “the ritual failed” if $c = 0$.

Hints

from qiskit_aer import AerSimulator
from qiskit import ClassicalRegister, QuantumCircuit, QuantumRegister, transpile
 
# Define or import before_oracle, oracle, and after_oracle here.
 
# Sample input
n: int = 3
A: int = 1  # A is odd
B: int = 4
 
# Build the quantum circuit.
x = QuantumRegister(n)
y = QuantumRegister(n)
c = ClassicalRegister(1)
main_qc = QuantumCircuit(x, y, c)
main_qc.compose(before_oracle(n), inplace=True)
main_qc.compose(oracle(), inplace=True)
main_qc.compose(after_oracle(n), inplace=True)
 
# Simulate the quantum circuit and retrieve the contents of register c.
simulator = AerSimulator()
job = simulator.run(
    transpile(main_qc, simulator),
    shots=1024,
)
counts: dict[str, int] = job.result().get_counts()
print(f"Measurement counts: {counts}")