For the record, here is an $\Omega(n^2)$ lower bound when your only access to the data is using queries of the form "$x_i = y_j$?". The proof uses an adversary argument. We will assume for convenience that $n$ is divisible by $8$.
We will maintain a bipartite graph, initially with $n$ nodes on each side, corresponding to $x_1,\ldots,x_n$ on one side and to $y_1,\ldots,y_n$ on the other. There is an edge connecting $x_i$ to $y_j$ if the algorithm hasn't found out that $x_i$ is different from $y_j$. Initially, the graph is complete. If we answer a query of the algorithm by $x_i \neq y_j$ (we will soon discuss our answering strategy), then we simply remove the edge $(x_i,y_j)$. If we answer a query by $x_i = y_j$, then we remove the vertices $x_i,y_j$.
Our answering strategy will always maintain the invariant that the current bipartite graph always contains at least two perfect matchings, and so the algorithm cannot tell how to match the $x$'s with the $y$'s. We will guarantee that by ensuring that all vertices have degree at least $n/2+1$. Let us explain why this guarantees the existence of at least two perfect matchings.
First, let us show that if all vertices have degree at least $n/2$ then there is at least one perfect matching. According to Hall's theorem, there is a perfect matching if every set $S$ on the left-hand side has at least $|S|$ neighbors on the right-hand side. This is clearly satisfied when $|S| \leq n/2$. If $|S| > n/2$ then every vertex on the right-hand side is a neighbor of $S$, since otherwise it will have degree less than $n/2$.
Suppose now that all vertices have degree at least $n/2+1$. Take any vertex $v$ on the left. If we choose any of its neighbors $u$ on the right and remove both, then the remaining graph still has minimum degree at least $n/2$. Hence there is a perfect matching in which $v$ is matched to $u$. Since $v$ has at least two neighbors, this shows that there are at least two different perfect matchings.
We now describe our answering strategy. The strategy proceeds in phases, starting with phase $0$. We move to next phase after each time we answer a query by $x_i = y_j$. We will maintain the invariant that in phase $t$, all vertices have degree at least $(3/4)n-t$. This implies that all vertices have degree at least $n/2+1$ as long as $t < n/4$.
Suppose that the algorithm asks "$x_i = y_j$?" during phase $t$. If both $x_i$ and $y_j$ have degree larger than $(3/4)n-t$, then we answer $x_i \neq y_j$. This clearly maintains the invariant. If one of them has degree exactly $(3/4)n-t$, then we answer $x_i = y_j$, and proceed to phase $t+1$. This also maintains the invariant, since we have decreased each degree by at most $1$.
As we have shown above, the algorithm cannot stop until reaching phase $n/4$, since in every earlier phase there are at least two perfect matchings consistent with the known information. It remains to lower bound the number of queries needed to reach phase $n/4$. We will actually lower bound the number of queries needed to reach phase $n/8$.
In order to reach phase $t$ from phase $t-1$, the degree of some vertex $v_t$ must reach $(3/4)n-t \leq (3/4)n$. So in order to reach phase $n/8$, the degree of $n/8$ vertices $v_1,\ldots,v_{n/8}$ needs to reach $(3/4)n$ or below.
The degree of a vertex can be decreased in two ways. When the algorithm answers $x_i = y_j$, the degrees of the neighbors of $x_i,y_j$ decrease by $1$; let us call this a major decrease. When the algorithm answers $x_i \neq y_j$, the degrees of $x_i,y_j$ decreases by $1$; let us call this a minor decrease. Since there are $n/8$ major decreases up to phase $n/8$, they can reduce the degree of $v_1,\ldots,v_{n/8}$ by at most $n/8$ each. Each of these vertices has to have its degree reduced using minor decreases by at least $n/8$. Since each minor decrease affects two vertices, there must be at least $(n/8)^2/2 = \Omega(n^2)$ minor decreases. In other words, the algorithm must make at least $\Omega(n^2)$ many queries.
Conversely, the problem can be solved using $\binom{n}{2} \leq n^2/2$ queries, by finding the correct match for the vertices on the left side one by one. Is this algorithm optimal? This is an interesting question for future work.