Optimization of simulations

Introduction

When you run an algorithm on a simulator, it is not usually necessary to end it with a measurement instruction. This section explains when it is better to omit the measurement, an approach that can drastically improve execution times.

Executing algorithms on hardware back-ends

When you run a quantum algorithm on a hardware backend the algorithm must be finalized with a measurement on one or more qubits in order to get the results of the measurement in the binary register. In most cases you will need to execute multiple shots in order to get some statistics on your measurement and to reduce the effects of decoherence, leakage and control imperfections. On a hardware backend, when you execute multiple shots of your algorithm, all of them will be executed back to back. For each shot, the final measurement results will be stored in the binary register and written to the raw data file; see displaying and downloading your results. The histogram will show the normalized frequency of each state of the binary register.

Executing algorithms on simulator back-ends

Deterministic algorithms

In a simulation we can determine the full quantum state of the system, therefore in most cases it is not necessary to perform a measurement, or even to run the algorithm multiple times, to determine all possible outcomes.

The Hello quantum world example is an example of such an algorithm. When you run it repeatedly, the final quantum state will always be the same. We will refer to such an algorithm as a deterministic algorithm. Most algorithms fall into this category.

q[0]
 
 
 
 
q[1]
 
 
 
 

In this example, assuming no measurement is performed, the final quantum state of the system is:

Φ+=00+112=1200+1211\vert\Phi^{+}\rangle =\frac{\vert 00 \rangle + \vert 11 \rangle}{\sqrt{2}} = \frac{1}{\sqrt{2}} \vert 00 \rangle + \frac{1}{\sqrt{2}} \vert 11 \rangle

In this case, the probability amplitudes for the 00\vert 00 \rangle state and 11\vert 11 \rangle state are both 12\frac{1}{\sqrt{2}} and the probability of measuring one of these states is 50% (which is the result of squaring its probability amplitude). The probability of each state is exactly what we show in the histogram, so one shot is enough to determine exactly the probability of each state:

0.500
00
0.500
11
1.0
0.8
0.6
0.4
0.2
0.0

Quantum Inspire uses a simple rule to determine whether an algorithm is deterministic or not. This rule does not cover all situations, but catches a large number of situations where the algorithm is deterministic and just one execution of the algorithm is sufficient. When the following two conditions are true, the algorithm is certainly deterministic:

  • The algorithm contains no measurement instruction (measure, measure_all, measure_z, measure_y, measure_x, measure_parity)
  • The algorithm contains no error_model instruction

Simulation optimization without randomization

When an algorithm is deterministic, Quantum Inspire will always execute just one shot of the algorithm to determine the full state of the system. The user will be offered two ways of generating the probability distribution histogram for the possible outcome states, using the field number of shots (N) on the pop-up window that appears after the RUN button is pressed from the editor view:

  1. N=1: The histogram will be determined directly from the final state probability amplitudes. This method is called simulation optimization without randomization.
  2. N>1: The histogram will be determined using a Monte Carlo simulation. This method is called simulation optimization with randomization.

Simulation optimization with randomization

When the user selects a number of shots N>1 the Monte Carlo simulation will do the following:

  1. For each possible outcome state, the probability will be determined (total probability =1)
  2. A bin is created for each outcome state, initialized with zero
  3. Each bin will be mapped to a number range between 0 and 1, based on the probability vakue for each bin. As an example: for the Bell state in the Hello quantum world example the bin 00 will be mapped to the range 0<x0.50 < x \leq 0.5 and the bin 11 will be mapped to 0.5<x10.5 < x \leq 1
  4. A random number between 0 and 1 is generated.
  5. The bin corresponding to the random number is increased by one
  6. Steps 3 and 4 are repeated N times
  7. The final state distribution is determined by normalizing the contents of the bins.

The result will be just as if you had executed the algorithm N times. Note that in this case, the distribution will get closer and closer to the result of the optimization without randomization with the uncertainty depending on the number of 'shots' (virtual shots). Such a simulation can be valuable for testing algorithms on a simulation back-end before running it on a hardware back-end.

Non-deterministic algorithms

It is important to realize the following: if we had added a measure_all statement at the end of the hello quantum world algorithm, the final state would have been different. Below we will show some examples explaining why the inclusion of a measurement instruction or an error model may lead to non-deterministic behaviour. In these cases simulation optimization is not possible and the user should execute multiple shots of the algorithm to to produce a probability distribution for the possible outcomes.

q[0]
 
 
 
 
 
 
q[1]
 
 
 
 
 
 

After the measurement, the final state of the system will be either:

[02][02]\left [ \frac{\vert 0 \rangle}{\sqrt{2}} \right ] \left [ \frac{\vert 0 \rangle}{\sqrt{2}} \right ]

or

[12][12]\left [ \frac{\vert 1 \rangle}{\sqrt{2}} \right ] \left [ \frac{\vert 1 \rangle}{\sqrt{2}} \right ]

In this case, the final state is not deterministic and we will have to execute multiple shots in order to produce a probability distribution for the possible outcomes.

Algorithms with an error model

When we include an error model in our algorithm, random errors will be introduced when it is executed and the final state may differ for each execution.

In this case, the final state is not deterministic and we will have to execute multiple shots in order to produce a probability distribution for the possible outcomes.

Algorithms with binary-controlled gates

Measurement instructions, together with binary-controlled gates, can be used to alter the flow of the algorithm. In this case, the final state is not deterministic and we will have to execute multiple shots in order to produce a probability distribution for the possible outcomes.

Note that binary-controlled instructions by itself, without previous measurements on the qubits, will not lead to a different state, because the corresponding binary register entries will be zero. Therefore Quantum Inspire checks for measurement instructions, not for binary-controlled gates.

Algorithms with measurements

Even a single measurement can lead to non-deterministic behaviour. As an example, try out the following code in Quantum Inspire:

        
          version 1.0
qubits 1
measure_x q[0]
        
      
q[0]
 

When you execute 1 shot of this algorithm and try this a few times in succession, you will notice that the outcome will be different every time. So, even a single measurement may result in a non-deterministic algorithm.

Edge cases

The rules that are used by Quantum Inspire to determine whether an algorithm is deterministic may sometimes cause an algorithm to be identified as non-deterministic when it is not. An example is the following code, where the measurements in line 4 have no impact on the final state of the system. In this case Quantum Inspire will prevent optimization of the simulation.

        
          version 1.0
qubits 2
prep_z q[0:1]
{measure_z q[0] | measure_x q[1]}
{x q[0] | c-x b[0],q[1]}
        
      
q[0]
 
 
 
 
 
 
q[1]
 
 
 
 
 
0
 

In cases like this, the algorithm can often be re-written in such a way that the measurement instructions are not needed.