# What is the relation between the database made up of N elements and the index made up of a string length n in the query model?

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$$?

• Try writing explicit examples with small values of n and fixed $X$. Then you can clarify your question. Mar 25 at 17:17