Sub-normal numbers for floating-point numbers with qubits as exponential.
In recent years, significant progress has been made in the development of quantum algorithms for linear ordinary differential equations as well as linear partial differential equations. There has not been similar progress in the development of quantum algorithms for nonlinear differential equations. In the present work, the focus is on nonlinear partial differential equations arising as governing equations in fluid mechanics. First, the key challenges related to nonlinear equations in the context of quantum computing are discussed. Then, as the main contribution of this work, quantum circuits are presented that represent the nonlinear convection terms in the Navier–Stokes equations. The quantum algorithms introduced use encoding in the computational basis, and employ arithmetic based on the Quantum Fourier Transform. Furthermore, a floating-point type data representation is used instead of the fixed-point representation typically employed in quantum algorithms. A complexity analysis shows that even with the limited number of qubits available on current and near-term quantum computers (<100), nonlinear product terms can be computed with good accuracy. The importance of including sub-normal numbers in the floating-point quantum arithmetic is demonstrated for a representative example problem. Further development steps required to embed the introduced algorithms into larger-scale algorithms are discussed.
- partial differential equations
- fluid mechanics
- nonlinear equations
- quantum Fourier transform
- floating-point arithmetic
Quantum computing  and quantum communication are research areas that have seen significant developments and progress in recent years, as is apparent from the work covered in this book. In this chapter, the focus is on the development of quantum algorithms for solving nonlinear differential equations, highlighting key challenges that arise from the non-linearity of the equations to be solved. For this application of quantum computing, progress has so far been relatively limited and in this work, a promising approach to deriving efficient quantum algorithms is proposed. Although the focus is on non-linear equations related to fluid mechanics, the approach put forward here is applicable to a much wider range of problems. Furthermore, in developing the proposed method, efficient quantum circuits involving floating-point arithmetic were created, in contrast to the more commonly used fixed-point arithmetic employed in a range of quantum algorithms. This aspect of the work described here should also be useful for a wider audience. In this work, the development of quantum algorithms for the nonlinear governing equations for fluid mechanics is described with a particular focus on representing the non-linear product terms in the equations. A key aspect of the derived quantum circuits in the present work is the (temporary) representation of the solution in the computational basis, along with the the use of a floating-point data representation in the arithmetic operations. The quantum circuits for obtaining the non-linear product terms are new developments and form the main contribution of this work. In recent years, a small number of works have considered quantum computing applications to fluid mechanics [2, 3, 4, 5, 6, 7, 8]. A brief review of this previous work will be presented in Section 2 and will provide context to the proposed approach. Related work on algorithms with representation in the computational basis is reviewed in this chapter. This chapter is structured as follows. Section 2 describes the background to the current work. Section 3 reviews the key challenges related to treating nonlinear differential equations in a quantum computing context, followed by a discussion of the nonlinear governing equations in fluids dynamics in Section 4. Section 5 then describes how nonlinear terms in governing equations can be evaluated in quantum algorithms using the computational basis. Section 6 and Section 7 discuss the quantum circuits used for computing the square of a floating-point number and the multiplication of two floating-point numbers, respectively. The simulation and verification of the derived quantum circuits is presented in Section 8. The complexity of the circuits is analyzed in Section 9. Finally, conclusions from this work and suggestions for further work are presented in Section 10.
2. Background of present work
For a small number of applications, quantum algorithms have been developed that display a significant speed-up relative to classical methods. Computational quantum chemistry is proving to be one of the key areas of application. Important developments for a wider range of applications include quantum algorithms for linear systems [9, 10] and the Poisson equation . Applications to computational science and engineering problems beyond quantum chemistry have only recently begun to appear [4, 5, 6, 12, 13, 14]. Despite this research effort, progress in defining suitable engineering applications for quantum computers has been limited.
Significant progress has been made in recent years in the development of quantum algorithms for linear ordinary differential equations (ODEs) as well as linear partial differential equations (PDEs) [15, 16, 17, 18, 19]. However, in contract to this progress for linear equations, there has not been similar progress in the development of quantum algorithms for nonlinear ODEs and nonlinear PDEs. An early work by Leyton and Osborne  presented an innovative and highly ambitious algorithm. However, the computational complexity of this work involves exponential dependency on the time interval used in the time integration. A small number of more recent works have addressed nonlinear differential equations and typically algorithms for very specific problems were obtained . Therefore, much research work is needed into quantum algorithms for a wider range of nonlinear problems.
Early work in quantum computing relevant to the field of Computational Fluid Dynamics (CFD) mainly involved the work on quantum lattice-gas models by Yepez and co-workers [2, 3]. This work typically used type-II quantum computers, consisting of a large lattice of small quantum computers interconnected in nearest neighbor fashion by classical communication channels. In contrast to these quantum lattice-gas based approaches, the present study focuses on quantum algorithms designed for near-future ‘universal’ quantum computers. The potential of quantum computing in the context of direct numerical simulation of flows was reviewed recently by Griffin et al. , showing that a number of further developments are needed to make this approach viable.
Typically, there are two methods of encoding the result of a quantum algorithm: encoding within the computational basis of the quantum state and encoding within the amplitudes of the quantum state. The widely-used Quantum Fourier Transform (QFT) uses the second approach. The QFT with complexity for problem size has exponential speed-up compared to the classical fast Fourier transform (complexity ) and plays an important role in quantum computation as an essential part of many quantum algorithms. The exponential speed-up realized is due to superposition and quantum parallelism. However, in same quantum algorithms, the Fourier coefficients may be needed in the computational basis .
Here, the two different encoding methods are illustrated using the discrete Fourier Transform (DFT). The QFT performs the DFT in terms of amplitudes as,
The QFT performs a DFT on a list of complex numbers, and the result is stored as amplitudes of a quantum state vector. In order to extract the individual Fourier components, measurements need to be performed on the quantum state vector. Therefore, the QFT is not directly useful for determining the Fourier-transformed coefficients of the input state. However, the QFT is widely used as a subroutine in larger algorithms. In contrast to the amplitude encoding in Eq. (1), Zhou et al.  presented a quantum algorithm computing the Fourier transform in the computational basis (termed QFTC). This quantum algorithm encodes Fourier coefficients with fidelity and digit accuracy for each Fourier coefficient. Its time complexity depends polynomially on , and linearly on and . The QFTC, enables the Fourier-transformed coefficient to be encoded in the computational basis as follows,
where corresponds to the fixed-point binary representation of using two’s complement format. In the algorithm proposed by Zhou et al. , the input vector is provided by an oracle such that,
which can be efficiently implemented if is efficiently computable or by using the qRAM that takes complexity under certain conditions . Comparing Eq. (1) and Eq. (2), it is clear that encoding in the computational basis requires a number of additional qubits depending on the required fixed-point representation.
3. Nonlinear problems on quantum computers
An early work by Leyton and Osborne  introduced a quantum algorithm to solve nonlinear differential equations with an unfavorable complexity. Since then, very few works have considered quantum algorithms for nonlinear equations. In contrast, algorithms for linear differential equations have continued to receive significant attention. As an example, advanced quantum spectral methods for differential equations were published recently by Childs and Liu .
A key contributing factor to the limited progress in algorithms for non-linear problems is the inherent linearity of quantum mechanics. For quantum algorithms encoding information as amplitudes of a quantum state vector, nonlinear (product) terms cannot be obtained by multiplying these amplitudes by themselves, as a result of the no-cloning theorem that prohibits the copying of an arbitrary quantum state. Furthermore, all quantum-gate operations (with the exception of measurements) in the quantum-circuit model used here need to be unitary and reversible. These requirements add further challenges to representing nonlinear terms when using the amplitude-based encoding approach. Specifically, in a normalized quantum state vector all amplitudes in the vector are (unless only a single amplitude is non-zero), therefore an operator performing products of the amplitudes cannot be unitary since the resulting quantum state vector will no longer have a unit norm.
One possible way around these problems associated with nonlinear terms would be a hybrid quantum-classical approach where the nonlinear products are computed on a classical computer. However, due to the complexity introduced by measuring the quantum state (needed before each transfer of information to the classical computer) and the cost of (re-)initialization of the quantum computer with the result of these products, this is not a promising line of development. It is highly unlikely to lead to a quantum speed-up. Recently, Variational Quantum Computing (VQC) was introduced as an effective hybrid classical-quantum approach [22, 23], firstly for applications in quantum chemistry and more recently for a wider range of linear and nonlinear problems . The VQC approach constructs the required solution from a layered network, as illustrated in Figure 1. As shown in Figure 1(a), multiple layers are used (in the illustration), each taking as input multiple qubits (6 in example shown). Using depth 5 in the example, the quantum circuits defined by involve 13 two-qubit gates as shown in Figure 1(b). Each of these gates has a parameter associated with it. A classical computer is used to create optimized parameters employing an iterative approach that takes the measured state of the ancilla qubit as input. A further key part of the approach is the problem-specific Quantum Nonlinear Processing Unit (QNPU). Recently, Lubasch et al.  published an example for the QNPU for the nonlinear Burgers equation. In applications of the VQC approach, the efficiency strongly depends on the choice of the number of parameters used in . The work by Lubasch et al.  showed that exponential speed-up is only possible if the depth of scales with the number of qubits and not with the overall problem size. It is clear that the proposed VQC approach is an important development toward QC applications to nonlinear problems. It therefore constitutes a leading candidate for applications to fluid dynamics. However, it is also clear that further investigation is needed to further assess its suitability for a range of applications.
4. Nonlinear governing equations in fluid mechanics
The Navier–Stokes equations for an incompressible, Newtonian fluid can be written as,
where , , and are the velocity, pressure, density and kinematic viscosity, respectively. denotes the coordinate in space. The second term on the right-hand side of Eq. (4) is the nonlinear convection term that poses a key challenge to developing efficient quantum algorithms for the Navier–Stokes equations. Efficient quantum algorithms for linear convection equations discretized on regular Cartesian meshes with periodic boundary conditions have been devised in recent years . When studying numerical methods for the Navier–Stokes equations, it is often useful to switch to Burgers’ model equation, to obtain a single nonlinear partial differential equation that retains a nonlinear convection term similar to the Navier–Stokes equations. Using the VQC approach, Lubasch and co-workers recently published example quantum circuits to model the Burgers equation . Griffin et al.  discuss two approaches for treating the nonlinear term in the Navier–Stokes equations: the VCQ approach of Lubasch et al.  and a linearized approach. These authors conclude that, at present, VQC represents the most promising approach for Navier–Stokes equations. Their study also highlights that much further research work is needed to create efficient algorithms for fluid dynamics applications. It is relatively easy to show that the linearization approach to solving non-linear governing equations on a Quantum Computer is generally unfeasible. In applying linearization to nonlinear governing equations, the idea is to use a linearization about the present state of the solution, and then advance this linearized problem in time. This creates a linearization error, which is small if the time step is small. However, even if this linearization error can be tolerated, the linearization approach is problematic in a quantum computing context. This is due to the need for repeated measuring of the quantum state (so that the gates that implement the linear operator may be updated with the current solution) and repeated re-initialization of the quantum state. The complexity associated with repeated measuring and re-initialization is so large that any benefit of a quantum algorithm over a classical algorithm is very likely to vanish.
The development of quantum algorithms for fluid dynamics is clearly at a very early stage and therefore it is essential that different approaches are considered.
5. Representing nonlinear terms in computational basis
In the present work, an alternative approach to introducing the nonlinear terms of nonlinear differential equations into a quantum algorithm is investigated. Specifically, the assumption is made that in a large-scale quantum algorithm for the solution of the nonlinear (partial) differential equations, the solution is encoded in terms of amplitude in the quantum state vector, i.e. the approach used in a wide range of algorithms including the QFT. Then, for the nonlinear terms of the equations, the following steps are suggested. First, within the larger quantum algorithm, a quantum algorithm is embedded that converts the solution from the quantum-amplitude representation to a representation in the computational basis. Recently, quantum algorithms for this ‘analog-to-digital conversion’ were published by Mitarai et al. . Using the representation of the solution in the computational basis, the required nonlinear terms are then efficiently evaluated using quantum circuits presented later in this chapter. Once computed, a conversion back to quantum-amplitude representation is to be used, enabling the rest of the quantum algorithm to proceed. For this ‘digital-to-analog’ conversion, quantum algorithms were recently studied and published by SaiToh . For the representation in the computational basis, a fixed-point approach is typically employed to represent real or complex numbers in quantum algorithms. The number of additional qubits required when using computational-basis encoding depends directly on the number of qubits required to represent the real and complex numbers needed in the algorithm. In the present work, a different approach is put forward: instead of using fixed-point arithmetic, a floating-point representation is used.
In the literature, quantum arithmetic using floating-point numbers has received very little attention so far. Haener et al.  described an investigation into quantum circuits for floating-point addition and multiplications and compared automatically generated circuits from Verilog implementations with hand-crafted optimized circuits. Their study provides evidence that floating-point arithmetic is a viable candidate for use in quantum computing, at least for typical scientific applications, where addition operations usually do not dominate the computation. Following on from these conclusions, the present work investigates the use of floating-point arithmetic as part of evaluating nonlinear terms in the computational basis.
5.1 Previous works on algorithms in computational basis
Quantum arithmetic in the computational basis constitutes an important component of many quantum algorithms, and as a result reversible implementations of algebraic functions (addition, multiplication, inverse, square root, etc.) have been widely studied. In contrast, there is relatively little work on quantum algorithm implementation of higher-level transcendental functions, such as logarithmic, exponential, trigonometric and inverse trigonometric functions. Examples of applications of trigonometric and inverse trigonometric functions in the computational basis can be found in the famous HHL algorithm  and in the state preparation algorithm introduced by Grover and Rudolph . More recently, a quantum algorithm for approximating the QR decomposition of a matrix in the computational basis was published by Ma et al. , with polynomial speed-up over the best classical algorithm.
5.2 Fixed-point and floating-point arithmetic
A fixed-point number held in an qubit register can be defined as the following quantum state,
where , . This state represents the number . The leftmost qubits are used to represent the integer part of the number and the remaining qubits represent its fractional part. In this example, no sign qubit is used so that only positive numbers can be represented (for most applications an additional sign qubit would be required). Since fewer than bits may suffice for the representation of the input, a number of the leftmost qubits in the register may be set to . Clearly, the fixed point system is very limited in terms of the size of the numbers it can store. Therefore, soon after computers were introduced for numerical computing the switch to floating-point arithmetic was made. In a computer implementation of a floating point number with base 2, a non-zero signed number , defined through a normalized representation, is expressed as,
where the numbers and are the mantissa and the exponent, respectively. The binary expansion of the mantissa is
Here, it is important to note that always for non-zero numbers in a normalized representation. This will be used in the present work to achieve savings in the number of required qubits, as detailed later. In the binary representation, the bits following the binary point are the fractional part of the mantissa. Once floating-point numerical computation on classical computers became commonplace, the industry standard IEEE 754 was introduced . A similar standard for floating-point representations on a quantum computer does not yet exist, but is desirable . A key feature of the IEEE standard is that it requires correctly rounded operations: correctly rounded arithmetic operations, correctly rounded remainder and square root operations and correctly rounded format conversions. Typically, rounding to the nearest floating pointing number available in the destination (output register) is used. In the quantum circuits in the present work, rounding down to nearest is used, for reasons of simplicity. Detailed analysis of quantum-circuits developed here for squaring and multiplication operations shows that ‘correctly’ rounding to nearest involves a significant increase in circuit complexity (i.e. using quantum equivalents of guard and sticky bits, that are well established in arithmetic on classical computers ). A key aspect of the IEEE 754 that has been incorporated in the present work is the definition of sub-normal numbers. To illustrate the concept of subnormal numbers, the IEEE 754 standard representation of single format numbers using a 32-bit word is considered. The first bit is the sign bit, followed by 8 bits representing the exponent. Then, 23 bits are used to store a 24-bit representation of the mantissa, i.e. is not stored. Numbers with exponent bits and are defined special cases. The smallest normalized number is . Sub-normal numbers are used to represent smaller numbers, i.e. in this case the exponent field has a zero bit string but the fraction field has a nonzero bit string. Zero is represented with a zero bit string for the fractional field. For all subnormal numbers, the used for the exponent represents and by using the fractional field bits, equally-spaced numbers in the range (with zero bits after the binary point) to (with 23 one bits after the binary point) are encoded.
5.3 Quantum floating-point format used in present work
Based on the floating point representation defined in the IEEE standard, the present work introduces a floating-point system with fewer bits (i.e. qubits in this case) than the 32 used for single format numbers. This is the direct result of the limited number of qubits available on current and near-term quantum computers. To optimize the range of floating-point numbers that can be represented with the approach used here, the following key aspects of the IEEE standard were adopted:
For the mantissa only the fractional part is stored,
Exponent bit strings and are used for special cases, i.e. dealing with , subnormal numbers as well as cases with overflow,
The remaining range of exponent bit strings is used for a range of exponential centred around ,
Sub-normal numbers are used to extend the range of small numbers,
Rounding down to nearest is used as rounding mode,
Only unsigned numbers are considered for simplicity. Signed numbers can easily be obtained by adding a further ‘sign’ qubit.
In this work, a floating-point number is represented as an quantum register. In the quantum-circuit implementation, the most significant (leftmost) mantissa qubit is not stored, using the hidden-bit approach used in the IEEE 754 standard. Therefore, qubits define the fractional part of the mantissa in the developed quantum circuits. defines the number of qubits used to define the exponent. In the following, examples with and and are considered. For , the number is defined by when . Similarly, defines the number for and . For , the smallest normalized number that can be represented is independent of the number mantissa qubits. Then, exponent state defines zero and sub-normal numbers, as shown in Table 1 for , and .
Similarly, using qubits for the exponent () means that the smallest normalized number is . For and , Table 2 shows the corresponding sub-normal numbers.
In line with the IEEE 754 standard, exponent state denotes numbers for which an overflow has occurred. For , the largest normalized number available is which equates to and for and , respectively. Similarly, for , the largest normalized number available is which equates to and for and , respectively.
6. Quantum circuits for squaring floating-point numbers
For a floating-point number defined by mantissa and exponent bits, a total of qubits is needed to define the state in the quantum circuits introduced here. An example with and will now considered, using registers and to define the fractional part of the mantissa and the exponent of the input number, respectively. For the multiplication operation described later a second input floating-point number is defined using and . The output of the squaring and multiplication operations is a floating-point number defined by and (initialized at ). In addition to the input and output registers, the quantum circuits will need additional qubits to hold results of intermediate results, e.g. for a -qubit sub-register is used. To facilitate the quantum-multiplication operations, a further ancilla qubit is used. For quantum circuits without measures to deal with sub-normal numbers and overflow, the quantum state for and is defined in a -qubit register
For and , the required number of qubits increases to . The quantum circuit performing the squaring operation for and is detailed here as example (in realistic applications will typically be needed). Figure 2 shows the quantum circuit used in the first step of computing the square of a quantum floating point with and . This step involves computing the square of the mantissa, with this result temporarily stored in . In this circuit, prepares this temporary register for the three subsequent product steps denoted by , and , involving doubly-controlled phase operations. Specifically, three-qubit gates are used applying a phase rotation conditional on state of and either or . The steps are controlled-summation operations in the shift-and-add approach to computing the products, i.e. the circuits in are derived from quantum adders controlled by an additional qubit. Once the controlled phase changes in the circuits , and have been applied, inverse on creates the desired output state. In case the square of the mantissa , i.e. , the result exponent needs to be incremented by . This is achieved by apply a controlled-NOT to (which was initialized at ) with as control. In the next step, result mantissa qubits are set using temporary results in , where the required gate operations are conditional on the state of . Then the steps shown in Figure 2 are ‘uncomputed’ so that the sub-register is set to again. The next step is illustrated in Figure 3, where the output exponent is obtained. This step involves the initialization of the temporary register with (i.e. twice the input exponent). Then, the bias of is removed (denoted by ). This bias removal uses two’s complement to create a modified modulo-5 adder that removes a value from . Then, the result exponent sub-register is prepared for the subsequent modulo-3 addition (denoted by ) by applying . Next, the modulo-3 adder is used to add the qubits into . By applying the inverse QFT3 on the required state is obtained. The remaining steps shown in the quantum circuit in Figure 3 are used to ‘uncompute’ and clean-up the temporary register, e.g. using inverse and a modified modulo-5 adder to re-apply the bias . The circuits described so far do not take into account the special situation arising from creating sub-normal numbers as output as well as cases with ‘overflow’ results. This is discussed next.
For certain normalized input numbers the squaring operation leads to outputs truncated to or to the non-zero sub-normal numbers discussed in Section 5.3. The quantum circuits discussed so far need to be modified in a number of ways to deal with this possible sub-normal output. Figure 4 illustrates the required changes for and . Two additional qubits are needed. Qubit is used as indication that result is a sub-normal number. Qubit is similarly used to define cases with output truncated to . Both qubits are initialized to . Then, before the mantissa multiplication step takes place, a first modification is introduced, shown on the left-hand side of Figure 4. For , only inputs with exponent will need truncating to , as shown in the first 4-qubit controlled-NOT gate flipping to . For , inputs with exponent are guaranteed to lead to sub-normal output (or ), and for these cases is set to , using the second 4-qubit controlled-NOT gate with as target. The mantissa-multiplication step shown in Figure 2 remains unchanged (i.e. qubits and are not used). The next required modification relates to the ‘copying’ of the result of the mantissa multiplication to output register and the application of increments to the output exponent. The additional logic needed is shown on the right-hand side of Figure 3. First, for , setting becomes conditional of both and . The next two 4-qubit gates are used to guarantee that correct output with exponent is created for inputs with exponents and . The remaining gate operations perform the ‘copying’ of the mantissa squared into taking into account the possible sub-normal output (cases with ). The steps for are the same as in the corresponding circuit for squaring without the sub-normal number modifications. A further set of circuit modifications to deal with sub-normal numbers is required in the quantum circuit used to obtain the output exponent. Figure 5 shows the additional operations required relative to the original quantum circuit shown in Figure 3. Three additional CNOT operations are introduced just before performing the . For and the initialization of is modified so that the subsequent steps will produce the correct result for the exponent. The three CNOT operations also appear in the ‘uncompute’ stage at the right-hand side of the circuit. Further changes comprise two -qubit controlled-NOT operations on and required to create exponents for inputs with exponent .
For a fixed value of it is important to note that the additional complexity introduced by increasing is limited. In fact, the quantum circuit shown on the left-hand side of Figure 4 does not depend on . Similarly, the quantum circuits used to obtain the result exponent are independent of . The circuit shown on the right-hand side of Figure 4, representing the definition of for cases with normalized or sub-normal output requires modification. Figure 6 shows how are set for using a set of gate operations that has grown linearly with . The circuit shown accounts for sub-normal numbers and includes underflow/overflow protection.
7. Quantum circuits for multiplication of floating-point numbers
In the interest of brevity, only the main features of the quantum circuits used for multiplication of two quantum floating-point numbers are summarized here. Figure 7 illustrates the quantum circuit used to compute the product of the mantissas of two inputs. Compared to the circuit shown in Figure 2 the main difference is that ancilla qubit is now set using the mantissa of a second input. A further difference relative to the squaring operation occurs in the circuit used to obtain the result exponent. Here, instead of setting the exponent using a bit shift, the sum of the two input exponents needs to be computed employing a quantum full adder.
8. Results of simulation and verification of quantum circuits
The proposed quantum circuits for squaring and multiplying floating-point numbers as part of the computational-basis representation, were systematically verified by gate-level simulation of the circuits for a wide range of cases with and without sub-normal numbers as well as cases with overflow results. The C++ quantum computer simulator detailed in previous work  was used for this purpose. To illustrate the process, the quantum algorithm used to square numbers with and is considered, with the following 19-qubit register (algorithm demonstrated accounts for sub-normal numbers as well as underflow/overflow protection, see Eq. (8) for reference):
where and define the exponent and the fractional part of the mantissa of the input, respectively. Qubits and are initialized as , while all other qubits are initialized as . The quantum state in the simulation is then initialized with a single non-zero (unit) amplitude, with the index in the quantum state vector defined by the binary representation of input exponent and fractional part of mantissa. With the rounding mode fixed at rounding down to nearest, the intended output can be easily computed before the quantum circuit is simulated. In effect, this defines the index of the single non-zero (unit) amplitude of the output quantum state that should be returned in case the circuit is correct. Upon finalizing the quantum computer simulation the actual quantum state vector obtained is compared against the previously-computed required output. For this verification to be meaningful, the following range of possible inputs and outputs were considered: (i) input and output are both normalized numbers, (ii) input is normalized number and output is a sub-normal number, (iii) input is a sub-normal number and result truncated to , (iv) input is a normalized number, with output overflow. For and , Table 3 summarizes the input and output states for examples of each of the categories considered. For inital and output the single non-zero amplitudes are shown. Since the simulator employed here stores the full state vector for qubits, only circuits with qubits were considered as a result of limited computational resources and the large number of cases considered (). For the squaring operation, and were considered, while for multiplication the range of needed to be reduced, i.e. .
|Input||Initial state||Output state|
9. Complexity analysis
Before analyzing the quantum circuits introduced here in terms of complexity, first the choice of and for representing realistic flow fields is considered.
9.1 Representing Taylor-green vortex flow
In a two-dimensional flow field, the non-linear terms appearing in the Navier–Stokes equations, shown in Eq. (4), involve the square of the velocity components in and directions, i.e. and , as well as, the product . Here, the example flow field defined by the two-dimensional Taylor-Green vortex is considered, where velocity and pressure are defined in a square domain with periodic boundary conditions as,
Considering a uniform mesh, the effect of representing the flow field variables with a reduced-precision floating-point format is analyzed first. Table 4 summarizes the results, highlighting the importance of including sub-normal numbers in the floating-point representation. Since a sign bit is not used here, the absolute values of were actually used. Flow variables defined in Eq. (10) are in the range , so that by increasing from to , far fewer sub-normal numbers are used to represent the flow field. As a result, removing the sub-normal number capability (as shown in bottom half of table), results in smaller errors for . For realistic applications of the proposed quantum floating point format, the relatively small overhead incurred by introducing sub-normal numbers in the quantum circuits clearly suggests that sub-normal numbers should be included.
|Rounding down - using sub-normal numbers|
|Rounding down - without sub-normal numbers|
For , the representation of and is considered. Specifically, the error shown is that introduced by the multiplication: the difference between the ‘exact’ product of the reduced-precision representation of and and the corresponding reduced precision representation of the products is shown in Table 5. The results highlight that although sub-normal numbers played a relatively smaller role in representing velocity components, in the computation of the nonlinear terms, the inclusion of sub-normal numbers is more important for the minimization of approximation errors.
|Rounding down - using sub-normal numbers|
|Rounding down - without sub-normal numbers|
9.2 Mantissa multiplication step
and inverse are used involving qubits, so that the complexity in terms of two-qubit (controlled-phase) gates scales as , where the well-known complexity of the standard implementation is used. The complexity of the phase-addition steps involved in the multiplication are detailed in Table 6. For the two-qubit gates the number can be seen to scale as , while the number of three-qubit gates shows a scaling.
9.3 Computation of exponent
and inverse are used involving , and qubits, representing a smaller complexity than the used in mantissa multiplications. The main contributions to complexity of exponent computation stems from the modulo and full-adders involving a number of qubits scaling linearly with . The polynomial complexity in terms of qubits for the adders implemented here is shown in Table 7.
The quantum circuits presented here for squaring two floating-point numbers in the format proposed show that by accounting for sub-normal numbers and under/overflow an additional number of multi-qubit controlled-NOT gates is needed. However, for the examples analyzed a polynomial dependence on and was observed. This means that in terms of quantum-algorithm complexity this implementation has the desired efficiency. The relatively small complexity as compared to circuits used for mantissa multiplication highlights that for most applications it is desirable to include the capability of using sub-normal numbers and provide under/overflow protection in the quantum circuits. The analysis in this section also shows that for a realistic application, a well-considered scaling of the governing equations to variables is even more important here than in classical implementations using IEEE single- or double-precision arithmetic. Using the limited number of qubits available on current and near-term quantum computers (), the proposed approach to introducing non-linearity is a good candidate in cases where and can be chosen significantly smaller than in equivalent classical floating-point representations.
The challenges associated with representing non-linear differential equations in terms of quantum circuits were discussed in this chapter. In this work, a new approach for representing product-terms in nonlinear equations suitable for near-term (e.g. NISQ generation) quantum computers was proposed. A key aspect discussed is the (temporary) representation of the variables in the computational basis. Furthermore, the use of a suitably-chosen floating-point format was detailed. The importance of including sub-normal numbers, such as defined in the IEEE 758 standard for floating-point arithmetic on classical computers, was demonstrated. Based on the current findings, a number of suggestions for further work can be put forward. The presented circuits performed arithmetic for a single set of input data, i.e. equivalent to data for a single point in a computational domain. Extending the approach to a multi-dimensional computational mesh is a first step to consider. A complexity analysis will be needed to assess the potential speed-up relative to classical discretization approaches for the considered equations. A further step involves investigating how the proposed approach can be made part of a larger quantum algorithm, where a mix of amplitude-based encoding and computational-basis encoding occurs. A key aspect is therefore the development of efficient quantum circuits to perform the required conversions between the two different encoding approaches. Finally, further work is needed to establish how the approach presented here can be used in a wider range of quantum computing applications.