I am working on a circuit model that contains a blackbox (query) and do not understand the relationship between what is in the black box and the way we get out the value of the element we index. The set up is that we have an $N$-bit input $X=(X_0......X_{(N-1)})\in\{0,1\}^N$ that can be accessed via an oracle: $O_x|i,b\rangle= |i, x_i \oplus b\rangle$ for $b\in\{0,1\}, i\in\{0,1\}^n$ The way I understand it is that we have $N=2^n$ inputs that are either $0$ or $1$. Then we use an oracle that takes an index $i$ that is made up of a string of $n$ $0$'s and $1$'s. Upon indexing, the value $x_i$ is XOR with the target bit and we are given a value $0$ or $1$.

My questions are : (1) what does the input look like (2) how are we able to index the N different inputs with only an n bit string and what does the index look like (3) are there then $2^n$ different n bit strings used for indexing (4) how does the register contain the index (that is a string) AND a single value $x_i$?

  • $\begingroup$ Try writing explicit examples with small values of n and fixed $X$. Then you can clarify your question. $\endgroup$
    – AHusain
    Commented Mar 25, 2022 at 17:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.