1
$\begingroup$

Consider the unitary matrix $A \in \mathbb{R}^{n^2\times n^2}$ which has only the first $n$ rows explicitly defined, with the remaining rows having some flexibility. $A$ can be written in block form as $ A= \left( {\begin{array}{cccc} B\\ C\\ \end{array} } \right) $ , where $B\in\mathbb{R}^{n\times n^2}$ and $C\in\mathbb{R}^{(n^2-n)\times n^2}$. The elements of $B$ are given by,

$ B_{ij}= \begin{cases} 1 & , \;\; i<n-1, \space j=i(n+1)+1 \\ 1 & , \;\; i=n-1, \space j=n^2-n \\ 0 & , \;\; \text{else} \end{cases} $

There are two restrictions on $C$, that are: 1) $C$ is the unitary complement to $B$ so $A$ is always unitary, and 2) the nonzero elements of $C$ cannot share a column with the nonzero elements of $B$.

Since this is a bit of an unusual matrix, here is an example for $n=4$. Note that $A$ is not unique because even though $B$ is fixed, there are many choices for $C$.

$ A = \left( {\begin{array}{cccccccccccccccc} 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{array} } \right) $

Where $B$ and $C$ are separated by the horizontal line.

My question is, given the definition of $B$ is there a choice for $C$ such that $A$ can be decomposed into $\mathcal{O} (poly(log(n^2)))$ one and two qubit gates?

My attempt at a solution was to force $A$ to be a permutation matrix as in the $n=4$ example above. This would allow me to decompose my matrix using only $SWAP$ gates. However, it appears that this is not efficient in general following this SE thread.

Improve this question
$\endgroup$
4
  • $\begingroup$ Just to be sure, $n$ is necessarily a power of $2$ here, since you're talking about qubits? $\endgroup$ Commented Oct 23, 2024 at 7:36
  • 1
    $\begingroup$ There's a solution with $\mathcal{O}(n\times\mathrm{polylog}(n))$ gates, but I'm unsure whether it's possible to do better, since it doesn't seem to be a "nice" structure $\endgroup$ Commented Oct 23, 2024 at 10:43
  • $\begingroup$ To answer your question, $n^2=2^Q$ where Q is the number of qubits. So yes, it is a power of $2$ and $Q$ must be even. Would you mind sharing your $\mathcal{O}(n\times \text{polylog}(n)))$ solution? $\endgroup$ Commented Oct 23, 2024 at 14:18
  • $\begingroup$ I've added the answer. If it doesn't fit your problem, tell me and I'll delete it! $\endgroup$ Commented Oct 23, 2024 at 15:09

2 Answers 2

Reset to default
3
$\begingroup$

If you look at what happens inside a specified row k, this matrix is moving the 1 from column k to column k*n+1. Then it does something special in row n-1. So this is an inverse-permutation corresponding to a multiplication, then an increment, then a fixup exchanging two states.

All those operations can be implemented in O(log^2 n) gates. In fact you can get down to O(log(n) log(log(n)) log(log(log(n)))) by using Schönhage–Strassen multiplication, though that would have bad constant factors.

Basically: the hard part of your problem is multiplication. Look up how to do modular multiplication, pick a prime P larger than n^2, and then look at the permutation you get by performing an inplace modular multiplication by the multiplicative inverse of n mod P. You'll see it has this each-row-advances-n-steps property you're looking for, which you can then tweak into a full solution.

enter image description here

Improve this answer
$\endgroup$
4
  • $\begingroup$ This is very encouraging and I'd like to spend the time to fully understand it. Following your direction. If I let $n=4$ then I can choose $P=17$. With this, the multiplicative inverse of $4 \: \text{mod} \:17$ is $13$ since $4*13=1 \: (\text{mod} \:17)$. However, I am clearly missing something because I don't see how this arithmetic relates to the "each-row-advances-n-steps" property that you mention. Would you mind elaborating a little bit more since this is unfamiliar to me? $\endgroup$ Commented Oct 23, 2024 at 17:23
  • 1
    $\begingroup$ Just try it $\endgroup$ Commented Oct 24, 2024 at 4:10
  • $\begingroup$ It appears that the $\times A \; \text{mod} \; R$ function advances the first $R$ rows $A$ steps when $R>A$. For example, here I advance the first $R=13$ rows $A=5$ steps each. However, there is also an undesired "wrapping" effect. You can see that in the 3rd row the element is at decimal $98$ instead of $111$ since it wraps around at the $R^{\text{th}}$ column. Similarly, the 4th row has the element at decimal $135$ instead of $148$. Is there a solution to this wrapping effect? $\endgroup$ Commented Oct 31, 2024 at 22:10
  • $\begingroup$ @thespaceman pick a bigger R $\endgroup$ Commented Nov 1, 2024 at 2:35
0
$\begingroup$

I am creating a new answer to add some detail to Craig Gidney's helpful response. As they mentioned, there are three basic steps:

  1. advance each row $n+1$ steps,
  2. fixup the $i=n-1$ row,
  3. increment all rows by $1$.

Let $Q=\text{log}(n^2)$ be the number of qubits where $n=\{4,8,16...\}$ to make $Q$ an integer.

For the first step, we can use inline multiplication to advance each row by $n+1$ steps when $n$ is even. Given the constraints of this problem, I can do this in $Q-1$ CNOT gates. For example, here are the circuits for n=4 and for n=8.

For the second step, we fixup the $i=n-1$ row by exchanging the $n^2-1$ column with the $n^2-n$ column. This is a two-level unitary permutation matrix and can be performed in at most $\mathcal{O}(Q^2)$ single qubit and CNOT gates following Nielsen and Chuang 2010 edition page 193. I don't have a general construction for this permutation matrix.

Finally, I use the most basic construction to increment each row by $1$ which requires $\mathcal{O}(Q)$ multi-controlled not gates to implement. For example, here is the increment circuit for the $Q=4$ qubit case.

Bringing everything together we have this circuit for the $n=4$ case. The first $n$ rows of my circuit match the matrix in my original question. The following $n^2-n$ rows do not match, but as I mentioned in the question, they can have any form as long as the full matrix is unitary. Though not a fully complete complexity analysis, the final complexity for the decomposition is: $\; (Q-1$ CNOT gates) + ($\mathcal{O}(Q^2)$ single qubit and CNOT gates) + ($\mathcal{O}(Q)$ multi-controlled NOT gates).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.