Recovers a hidden n-bit string s from f(x) = s·x (mod 2) in one query.
Classically you need n inner-product queries. The quantum circuit is Deutsch-Jozsa with a different oracle: CX from each wire where s has a 1 onto the |−⟩ ancilla.
Qubi bitstrings are MSB-left. Secret 101 means s₂=1, s₁=0, s₀=1, so CX from q2 and q0. After the final H on the inputs, those wires read s in the computational basis.
How it works
-
1
Ancilla |−⟩
X 3; H (0,1,2,3).
-
2
Oracle
CX [2,3]; CX [0,3] implement s·x for s = 101.
-
3
Read s
H (0,1,2). Inputs become |101⟩.
Default Qubi (static)
X 3 H (0,1,2,3) CX [2,3] CX [0,3] H (0,1,2)
Function form: BV(0b101)
Circuit
Expected result
State. Inputs |101⟩. Ancilla |−⟩.
P(q2 q1 q0 = 101) = 1. The secret is the input register, not the ancilla.
| Basis | Amplitude | Probability |
|---|---|---|
|0101⟩ (q3...q0, ancilla |0⟩ piece) |
1/√2 |
|
|1101⟩ |
−1/√2 |
Notes
- LSB of the secret maps to q0. That matches 0b... literals and BV() in the function library.
- A 0-bit in s contributes no CX.
Change parameters
The write-up above is for the default circuit. Use this control to generate other variants and load them in the simulator.