Introduction to adiabatic quantum computation

Author: Yiming Ding

Last update: Jan 9, 2024

1) Introduction

Though the relation between BQP and NP has not been understood clearly, it is expected that quantum computation can solve problems that are intractable for classical computation. Adiabatic quantum computation (AQC) serves as one of the paradigms (computational model) for quantum computation, which utilizes the well-known quantum adiabatic theorem, and has achieved fast development in decades [1, 2].

In this page, I will take a simple satisfiability (SAT) problem as an example, to show how AQC can be implemented to mathematical problems. It is assumed that you have had some basic knowledge of quantum mechanics and quantum computing especially the unitary gates and quantum measurement. Classical simulation of quantum circuits with programming will also be introduced for validating the efficacy of our algorithm, therefore you should better have some programming experience as well.

2) SAT problem

A logical form is called a conjunctive norm form (CNF) if it takes the form like

where are all boolean variables.

When all brackets have and only have terms inside, we call this kind of CNF a -CNF.

A -SAT problem is thus to find the solution to a -CNF. For better illustration, we consider a 2-SAT problem in this tutorial, but one should keep in mind that when , the problem is NP-complete.

As a specific example, we consider three boolean variables and for convenience, we use 0 to denote false and 1 to denote true. The CNF is taken to be

One can easily determine the solution for this demo problem via enumerating and obtain the two sets of solutions and . Next, we will see how to solve this problem via AQC.

3) Quantum adiabatic theorem

The archetypal Hamiltonian of AQC is

where relates to the problem we care and is some auxillary Hamiltonian which uncommutes with .

Initially, we set , i.e. , and prepare the ground state of . Then we slowly increase to monotonically. The quantum adiabatic theorem states that as long as this process is sufficiently slow, we can obtain the ground state of finally. For more details of this procedure, one can refer to [1].

4) Mathematical mapping

The key idea here is to encode the solution as the ground state of , then we can start from some easy-to-prepare and finally obtain the solution.

Consider the mapping

where is the Pauli operator on the -axis.

Notice that for , iff and can be false. Therefore we punish this possibility by constructing a punishment

for which the case that , or , is an excited state.

Simiarly, we can construct

Then our goal becomes finding the ground state of

Take

where is the Pauli operator along -axis.

Therefore, under Trotter-Suzuki expansion, the evolution operator becomes

which can be rewritten by a series of rotation gates and CNOT gates.

The ground state of is , where

which can be prepared with NOT gates and Hadamard gates.

5) Coding

Since mathematically, the operation of acting a quantum gate on a quantum state is some linear algebras, we can simulate such a process on a classical computer, which is a good way to check whether our algorithm is correct when we have no quantum computer on hand.

However, this method can simulate only up to around 30 qubits in general, which is analogous to the capacity of the exact diagonalization method in quantum many-body physics.

Here I use a popular quantum programming toolkit called QuEST, which is based on C/C++ language. You can also use other toolkits/frameworks like TensorCircuit (recommended) and Qiskit, which are all Python-based.

I will not go over the details of the related APIs of QuEST in my code which you may refer to their documents. The main target of this part is to show you the procedure of quantum programming.

First, we have to initialize the circuit. In QuEST, this can be done by

1
2
3
4
5
int nQ = 4;         // number of qubits
QuESTEnv env = createQuESTEnv();
Qureg circ = createQureg( nQ, env );
Qureg workspace = createQureg( nQ, env );
initZeroState( circ );

where we assign 4 qubits and the 0th qubit is our ancilla:

1
#define a 0     // label of the ancilla

Also we have to destroy the environment in the end of our program:

1
2
destroyQureg( circ, env );
destroyQuESTEnv( env );

Regarding the circuit, initially, we prepare the state by:

1
2
3
4
for ( int i = 0; i < 4; ++i ) {
  pauliX( circ, i );
  hadamard( circ, i );
}

then evolve it with:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int pair[][ 2 ] = {
  { 1, 2 },
  { 2, 3 },
  { 1, 3 }
};

double dt = 0.05;    // evolution time in each step
double step_size = 0.0005;      // variation of s in each step
auto N = int( 1 / step_size );
double s = 0.0;

for ( int n = 0; n < N; ++n ) {
  s += step_size;
  // H_1
  for ( int i = 1; i < 4; ++i )
    rotateX( circ, i, 2 * ( 1 - s ) * dt );
  // H_{f_1}
  for ( int j = 0; j < 2; ++j )
    controlledNot( circ, pair[ 0 ][ j ], a );
  rotateZ( circ, a, -2 * s * dt );
  for ( int j = 1; j > -1; --j )
    controlledNot( circ, pair[ 0 ][ j ], a );
  // H_{f_2} and H_{f_3}
  for ( int i = 1; i < 3; ++i ) {
    for ( int j = 0; j < 2; ++j )
      controlledNot( circ, pair[ i ][ j ], a );
    rotateZ( circ, a, 2 * s * dt );
    for ( int j = 1; j > -1; --j )
      controlledNot( circ, pair[ i ][ j ], a );
  }
}

where dt and step_size are usually some hyperparameters to assure the adiabacticity if we have no pre-information about our Hamiltonian.

In the end, we perform the measurements

1
2
3
4
5
6
int outcome;
cout << "Outcome of the measurement:\n";
for( int i = 1; i < 4; i++){
  outcome = measure( circ, i );
  cout << "\tq" << i << " = " << outcome << endl;
}

and one of the two possible results is 

1
2
3
4
Outcome of the measurement:
        q1 = 0
        q2 = 0
        q3 = 1

which corresponds to 

1
2
3
4
Solutions:
        x1 = 1
        x2 = 1
        x3 = 0

References

[1] E. Farhi et al. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106.

[2] Kostas et al. A Review on Quantum Approximate Optimization Algorithm and its Variants. arXiv:2306.09198 [quant-ph].