Скрытый сдвиг с преобразованием Фурье и без него

Булевы функции удовлетворяют $g(x)=f(x\oplus s)$, где требуется найти скрытую четырёхбитную строку s. Сложение и скалярное произведение здесь выполняются по модулю 2. Оракул без выходного кубита действует фазой $U_f|x\rangle=(-1)^{f(x)}|x\rangle$; вариант с выходом действует как $O_f|b,x\rangle=|b\oplus f(x),x\rangle$.

Авторская hsp_oracle принимает целый seed и логические output, shifted, fourier_transformed и возвращает оракул с четырьмя входными кубитами. В исходной заготовке n=4, seed=137; её программа и полная восстановленная функция приведены ниже. Определение f в этой функции — $f=x_0x_2\oplus x_1x_3$, в отличие от другого примера в объяснении главы.

1. Найдите s квантовым алгоритмом с доступом к преобразованной функции $\widetilde f$.
2. Решите ту же задачу без доступа к $\widetilde f$.

Контекст алгоритмов: первый применяет $H^{\otimes4}$, затем $U_g$, снова H, затем $U_{\widetilde f}$ и снова H. Во втором выход b сначала равен 0, входы переводятся H в равномерную суперпозицию, затем идут $O_f$, Z на b, $O_g$ и H на входах. Каждое измеренное (b,y) даёт уравнение $s\cdot y=b$; собираются независимые уравнения. Исходные места Your codes Here и проверки сохранены целиком; недостающие действия внутри них — часть задания.

Original imports, starters and result checks:

# initialization
import numpy as np

# importing Qiskit
from qiskit import IBMQ, Aer, QuantumCircuit, transpile, assemble
from qiskit.providers.ibmq import least_busy

# import basic plot tools
from qiskit.visualization import plot_histogram

from qiskit_textbook.problems import hsp_oracle
# Example usage
n = 4
seed = 137
oracle_f_tilde = hsp_oracle(seed, output=False, shifted=False, fourier_transformed=True)
oracle_g = hsp_oracle(seed, output=True, shifted=True, fourier_transformed=False)
qc = QuantumCircuit(n+1)
qc.append(oracle_f_tilde, [i+1 for i in range(n)])
qc.append(oracle_g, range(n+1))
qc.draw('mpl')

hsp_circuit = QuantumCircuit(n)

####################
# Your codes Here

####################

# Display circuit
hsp_circuit.draw('mpl')

# Check the result
aer_sim = Aer.get_backend('aer_simulator')
transpiled_hsp_circuit = transpile(hsp_circuit, aer_sim)
qobj = assemble(transpiled_hsp_circuit, aer_sim)
results = aer_sim.run(qobj).result()
answer = results.get_counts()

plot_histogram(answer)

hsp_circuit = QuantumCircuit(n+1)

####################
# Your codes Here

####################

# Display circuit
hsp_circuit.draw('mpl')

# Check the result
aer_sim = Aer.get_backend('aer_simulator')
transpiled_hsp_circuit = transpile(hsp_circuit, aer_sim)
qobj = assemble(transpiled_hsp_circuit, aer_sim)
results = aer_sim.run(qobj).result()
answer = results.get_counts()

plot_histogram(answer)

Recovered original hsp_oracle:

def hsp_oracle(
    seed: int, 
    output: bool=False, 
    shifted: bool=False, 
    fourier_transformed: bool=False
) -> QuantumCircuit:
    """
    Returns 4-qubit hidden shift problem oracle according to input options.
    Args:
        seed (int): the seed for the random shift string s.
        output (bool): if true, returns a 5-qubit circuit with the output register.
        shifted (bool): if true, apply the shift operation on both sides of the function.
        fourier_transformed (bool): if true, apply the Fourier transformed function instead.
    Returns:
        QuantumCircuit: oracle circuit with 4-qubit if ouput==False, 5-qubit if output==True.
    """
    
    np.random.seed(seed)
    s = f'{np.random.randint(0, 2**4):4b}'
    s = s[::-1]
    n = 4
    oracle = QuantumCircuit(4+output)
    
    # Apply the shift operation according to 'shifted'
    if shifted:
        for i in range(n):
            if s[i] == '1':
                oracle.x(i+output)
    
    # Apply the function according to output
    # f(x, y) = x·y = tilde f(x, y)
    if output:
        oracle.ccx(1,3,0)
        oracle.ccx(2,4,0)
    else:
        oracle.cz(0,2)
        oracle.cz(1,3)
    
    # Apply the shift operation according to 'shifted'
    if shifted:
        for i in range(n):
            if s[i] == '1':
                oracle.x(i+output)
    
    # Name the oracle
    if shifted and fourier_transformed:
        oracle.name = 'Oracle g tilde'
    elif shifted:
        oracle.name = 'Oracle g'
    elif fourier_transformed:
        oracle.name = 'Oracle f tilde'
    else:
        oracle.name = 'Oracle f'
    
    return oracle.to_gate()