9
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
+50
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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"

enter image description here

I have a tested implementation of this QROM in Q-sharp on github.

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.

enter image description here

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

$\endgroup$
2
  • $\begingroup$ Thank you very much. Can you briefly show the circuit for implementing the whole arcsin circuit, in order to assign the bounty? $\endgroup$
    – incud
    Jul 1 at 10:15
  • $\begingroup$ @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. $\endgroup$ Jul 1 at 10:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.