# Quantum implementation of arcsin

I am looking to implement a quantum version of the arcsinus function. Such a problem is motivated by the HHL algorithm where $$x\mapsto 1/x$$ and $$\arcsin$$ can be used to get $$1/x$$ from the computational basis state into the amplitude.

My questions are based on the paper Optimizing Quantum Circuits for Arithmetic (arxiv link :https://arxiv.org/abs/1805.12445). Their idea is to use a polynomial approximation of the function $$f$$ and to partition the domain $$\Omega$$ of study of $$f$$ : $$\Omega = \bigcup_{i=1}^M \Omega_i \quad \Omega_i\cap \Omega_j = \emptyset \, \forall i \neq j$$ and then perform a case distinction for each input, evaluating a different polynomial for $$x\in \Omega_i$$ and $$y\in \Omega_j$$, $$i\neq j$$. $$M$$ is chosen in order to achieve a certain precision and the degree of the polynomials are all bounded by a constant $$d$$.

Evaluating a single polynomial $$P(x) = \sum_{i=0}^d a_ix^i$$ can be done using the Horner scheme, where one iteratively performs a multiplication by $$x$$ and an addition by $$a_i$$ for $$i\in \{d, d-1, \cdots 0\}$$ :

$$a_d \mapsto a_dx+a_{d-1} \mapsto a_dx^2+a_{d-1}x + a_{d-2} \mapsto \cdots \mapsto P(x)$$

At iteration $$i$$, the last iterate is added by $${a_i}$$, while this does not represent any difficulty in classical computing, a register has to hold the set of coefficients $${a_i}$$, and has to be changed at each iteration. In their paper, the authors assume that $$\mathrm{NEXT}_a$$ implements such an operation.

My question : How can one implement efficiently the function $$\mathrm{NEXT}_a$$ ?

Qiskit contains a method to approximate $$\arcsin$$ and other smooth functions using the techniques described in the mentioned paper (arXiv:1805.12445) in PiecewiseChebyshev class. A key component in the implementation is the PiecewisePolynomialPauliRotations class.

To use Qiskit's implementation:

import numpy as np
from qiskit import *
from qiskit.circuit.library.arithmetic.piecewise_chebyshev import PiecewiseChebyshev

# number of state qubits:
N = 2

# The function to be implemented:
func = lambda x: np.arcsin(1 / x)

degree = 2
breakpoints = [2, 4]

pw_approx = PiecewiseChebyshev(func, degree, breakpoints, N)
pw_approx._build()

num_ancilla_qubits = pw_approx.num_ancillas

qc = QuantumCircuit(pw_approx.num_qubits)
qc.h(list(range(N)))
qc.append(pw_approx.to_instruction(), qc.qubits)


If you want to go through the implementation details, you can access the source code from here: 1 & 2.

How can one implement efficiently the function $$\text{NEXT}_a$$?

According to the paper, $$\text{NEXT}_a$$ is just switching between loaded data that is indexed by the $$\ell$$ register:

$$\text{NEXT}_a$$ changes the register to hold the next set of coefficients $$\sum \ell |\ell \rangle |a_\ell,i−1\rangle → \sum \ell |\ell \rangle |a_\ell,i−1\rangle$$

In other words, there is some classical data that is indexed by a quantum register $$\ell$$ and a classical index $$i$$. We're unloading the data for index $$i-1$$ and loading the data for index $$i$$. (Alternatively, the difference between them is being xored into register.) Loading/unloading/xoring classical data indexed by a quantum register is done using what are called "QROM circuits".

There's a simple space efficient QROM defined in "Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity"

If you have additional space available (including borrowed dirty qubits) you can use techniques from "Trading T-gates for dirty qubits in state preparation and unitary synthesis" to get the T count down from O(num_addresses) to O(sqrt(num_addresses * output_size)), assuming that's smaller.

It looks like there's also qsharp code for this one on github.

• Thank you very much. Can you briefly show the circuit for implementing the whole arcsin circuit, in order to assign the bounty? Jul 1 '21 at 10:15
• @incud Your question was summarized at the end as being just about the index. Doing the whole thing is quite a lot of work. I'd check existing libraries for implementations; Q# might have one since microsoft people wrote several of the related papers. Jul 1 '21 at 10:28