# How to keep track of entanglements when emulating quantum computation?

I am trying to build a quantum computation library as my university project. I am still learning all the aspects of the Quantum Computing field. I know there are efficient libraries already for quantum emulation. I just want to make my own, which will help me to grasp some of the core concepts of Quantum Computing.

I know that $n$ qubits can be stored with a $2^n$ element complex array. Also, a $n$ qubit gate is a $2^n \times 2^n$ 2D array. So, the following are my doubts (mostly related to entanglement):

1. When do I need to find the tensor product of gates (like $I \otimes H \otimes I$, for a $3$ qubit system)? Is it always necessary to compute the tensor product of order $2^n \times 2^n$, even if the qubits are not entangled?

2. With only a $2^n$ element array (which I store the coefficients), can I actually somehow calculate which qubits are entangled? Or do I need to make another data structure to store the entanglement information of my $n$ qubits (about which qubits are entangled)?

3. Is my 2nd question actually relevant? Do I need to keep track of the entanglement information at all? I mean, I don't know whether multiplying gates with coefficients is enough (even if the system is entangled). Maybe it is relevant at the time of measurement only.

• It depends on $n$ whether optimizing to keep track of entanglement pattern is premature or not. If you just have 3 qubits, then you're not gaining much by putting that effort in so it would be "premature optimization." So ask yourself, how scalable do you actually need this to be. – AHusain Apr 28 '18 at 17:21
• @MidhunXDA "I know what is happening physically, but I am not able to convert that to mathematical form". As far as I'm aware, there are multiple physical processes that lead to quantum computation. I think it would be a good idea if you precisely describe one of those physical processes which you want to emulate (or all of them, if you think that would still be in the scope of the question). I think that specifying this makes the question clearer and easier to answer. – Discrete lizard Apr 29 '18 at 9:04
• Please split this up into multiple questions - I see at least three distinct ones. – heather Apr 29 '18 at 16:01
• @heather I agree with the poster that these are really all questions that are different aspects of the same thing. I don't really see how to improve the question, but I believe I understand it well enough to give an answer. – DaftWullie Apr 30 '18 at 16:13
• @heather I strongly recommend moderators to not put questions on hold by themselves except in extreme cases (read: blatantly off-topic or spam). This question, although slightly broad can be reasonably answered in a single post. FWIW there are basically two questions here: 1) When to compute tensor products of gates? 2) How to take into account the effect of entanglement while doing so? – Sanchayan Dutta May 1 '18 at 6:21

It is certainly sufficient to always calculate the full $2^n\times 2^n$ unitary matrix, and then apply it to the $2^n$-entry state vector. If that's what you choose to do, that's all you have to do as all the entanglement information is contained in that vector. A quick and easy way to see if a particular qubit is entangled is to take the partial trace of your (pure) state vector over all other qubits. If the resulting matrix is rank 1, that qubit is in a separable state, otherwise it's entangled.

I assume the point of your question is really "How can this huge computational cost be avoided?". In general, it can't - if you're making use of the full power of the quantum computer, you will always need the $2^n$-entry state vector. However, there are various tricks that reduce the computational cost, such as delaying the need for such a large state vector by keeping track of the entanglement.

## Efficiency Improvements

The biggest saving that you can make compared to the naive implementation above is to avoid the $2^n\times 2^n$ unitary matrices. For example, if you are only using 1- or 2-qubit gates, simply using the sparsity of matrices means you only need $O(2^n)$ storage instead of $O(2^{2n})$.

Then there are other tactics that you can employ. For example, imagine you want to apply the two-qubit unitary gate $U$ on qubits $i$ and $j$. You can take sets of 4 elements from your state vector ($|x\rangle_{1,2,\ldots n\setminus i,j}|y\rangle_{i,j}$ for fixed $x\in\{0,1\}^{n-2}$ by taking all different $y\in\{0,1\}^2$) and just applying the $4\times 4$ unitary $U$ on that 4-element vector. Repeating this for every $x$ will return $U$ enacted on the original state vector.

I imagine there are other strategies one could come up with. The one that suggested itself from the original question was entanglement tracking. This gives memory and speed improvements at the start of a computation, but ultimately ends up being equivalent because (presumably) everything in the quantum computer will end up entangled.

## Entanglement Tracking

Let's assume that your computation consists of only unitary evolution and measurement on the set of $n$ qubits, i.e. there is no decoherence, probabilistic maps etc. Let's further assume that you start from a fully separable state such as $|0\rangle^{\otimes n}$. At this point, every qubit is separable, and it is sufficient to keep $n$ different registers, each conveying the state of a separable qubit. If your first gate is just a single-qubit operation $U$ on qubit $i$, then you just update the state stored on qubit $i$ as $|\psi_i\rangle\mapsto U|\psi_i\rangle$, and you don't have to touch anything else.

If you want to do a two-qubit gate $V$ between qubits $i$ and $j$, say, then you have to combine the states at both sites. So, you replace two registers each of dimension 2 with one register of dimension 4, containing state $V|\psi_i\rangle|\psi_j\rangle$. The problem is that you now can't split this state up again, so you have to keep those two qubits in a register forever after. Of course, if you ever have a 1-qubit gate $U$ to apply on qubit $i$, you'll now have to apply $|\psi_{i,j}\rangle\mapsto U\otimes\mathbb{I}|\psi_{i,j}\rangle$. Then, the next time you want a 2-qubit gate between, say, $j$ and $k$, you'll have to combine the spaces for $(i,j)$ and $k$. Those spaces will keep growing, but if a gate is localised on just one space, you only have to apply it there (using $\mathbb{I}$ operators to pad it on the rest of the qubits), and you don't have to do anything to the other spaces.

If you're doing things like this, you will not have (at least for the first few steps of your algorithm) a single $2^n$ element register. You'll have to have a bunch of different registers, and keep track of which qubits are described by which register in a separate array. Each time you combine the spaces of some qubits, you'll update that extra array.

Here's some very crude pseudo-code that may help to convey my meaning:

#initialise variables
entangled_blocks={{1},{2},{3},...,{n}}
quantum_states={{1,0},{1,0},...,{1,0}}

#apply action of each gate
for each gate
for each gate_target
target_block=entangled_blocks entry containing gate_target
next gate_target
if all target_blocks equal then
apply gate on target_block (pad with identity on other qubits)
else
new_entangled_block=union(target_blocks)
new_state_vec=tensor_product(quantum_states for each target block)
apply gate on new_state_vec (pad with identity on other qubits)
replace all target_blocks in entangled_blocks with new_entangled_block
replace all quantum_states(all target blocks) with new_state_vec
end if
next gate


## Other Options

(By no means exhaustive)

You may be interested to read about Matrix Product States which are a nice way of encapsulating the information about not-too entangled states, and that may provide an alternative route for you, depending on exactly what it is that you're trying to achieve.

• What I am trying to achieve is of course efficiency. Also, I want to know exactly how all these processes working (cus I am a noobie). So, in a practical, the better choice is just storing all the qubits coefficients together in a single array(record), right? Thank you for answering. – Midhun XDA May 2 '18 at 17:41
• @DaftWullie Your first sentence gives the impression that in general it would be required to store the full $2^n\times 2^n$ unitary, rather than just the $2^n$ vector. – Norbert Schuch May 2 '18 at 20:50
• @MidhunXDA In terms of efficiency, everything is essentially equivalent because a quantum computer will eventually cause everything to be entangled. To learn what is going on, you're probably better starting with the single array corresponding to the state vector. But, by using entanglement tracking you can gain some speed and memory improvements that should enable slightly longer simulations. – DaftWullie May 3 '18 at 6:10
• @NorbertSchuch I said it was "sufficient" to do that, which is true. I've added some further detail about how to avoid it. You probably know of other, better tactics. – DaftWullie May 3 '18 at 6:11