7
$\begingroup$

Does anyone know how to make a quantum circuit to compute exponentials where the exponent can be a fraction? To be more precise, I'm looking for a fixed point quantum arithmetic circuit that does the following:

$$|\vec{x}\rangle|\vec{0}\rangle \rightarrow |\vec{x}\rangle|e^x\rangle$$

where $|\vec{x}\rangle = |x_2x_1x_0x_{-1}x_{-2}\rangle$ is a $5$ qubit register, $|\vec{0}\rangle$ is an $n$ qubit register and where $x$ represents the binary number $$x = x_2\times 2^2 + x_1\times 2^1 + x_0\times 2^0+x_{-1}\times 2^{-1}+ x_{-2}\times 2^{-2}$$

and where $|e^x\rangle$ holds the fixed point representation of $e^x$ to within an error of $\epsilon$ (therefore the value of $n$ will be chosen based on the value of the desired $\epsilon$)

$\endgroup$
4
  • $\begingroup$ So $x$ is a 5-bit number, and $e^x$ is the exponential of it, which is could be 6-bits if $x_2=1$? How would the 6-bit number be defined if $x$ is defined in that symmetric way which requires an odd number of bits? Maybe 6-bit numbers have to be represented by something more bits long even if some bits aren't needed. Good luck with the question and +1 ! $\endgroup$ Mar 25 at 20:34
  • $\begingroup$ Ah right that's why I have defined $|\vec{0}\rangle$ as an $n$ bit register but I can see how that could be made more explicit in my question. I have added a bit of clarity to the question. Thanks for pointing that out! $\endgroup$ Mar 25 at 20:38
  • 1
    $\begingroup$ Another method could be to take the taylor expansion and then use a polynomial encoding circuit to encode this in the amplitude using rotations (see section D, static-content.springer.com/esm/…, for encoding polynomials into amplitudes). You can then use QFT^-1 to encode this value into a register. $\endgroup$
    – Sam Palmer
    Mar 30 at 18:59
  • $\begingroup$ As an aside, for $x<0$ here is a paper implementing a polynomial approximation method arxiv.org/abs/1805.12445 (as most people assumed correctly I am interested in the case when $x>0$ but I thought that maybe someone looking up this question might find this useful too) $\endgroup$ Apr 14 at 12:31
4
$\begingroup$

If $x$ is only 5 bits long, your best bet is almost definitely to just encode all the possible answers into a QROM circuit and do a lookup.

Here's a QROM circuit diagram from https://arxiv.org/abs/1805.036621:

enter image description here

And here's Q# source code for constructing a lookup circuit, from ancillary files of https://arxiv.org/abs/1905.076821.

/// # Summary
/// Performs 'a ^^^= T[b]' where 'a' and 'b' are little-endian quantum registers
/// and 'T' is a classical table.
///
/// Bits in 'T[b]' beyond the range of 'a' are ignored.
/// It is assumed that the address will never store a value beyond the end of the table.
/// Invalid addresses cause undefined behavior.
///
/// # Input
/// ## lvalue
/// The target of the xor. The 'a' in 'a ^^^= T[b]'.
/// ## table
/// The classical table containing integers to choose between and xor into the target.
/// The 'T' in 'a ^^^= T[b]'.
/// ## address
/// Determines which integer from the table will be xored into the target.
/// The 'b' in 'a ^^^= T[b]'.
operation XorEqualLookup (lvalue: LittleEndian, table: BigInt[], address: LittleEndian) : Unit {
    body (...) {
        Controlled XorEqualLookup(new Qubit[0], (lvalue, table, address));
    }
    adjoint self;
    controlled (cs, ...) {
        if (Length(table) == 0) {
            fail "Can't lookup values in an empty table.";
        }

        // Drop high bits that would place us beyond the range of the table.
        let maxAddressLen = CeilLg2(Length(table));
        if (maxAddressLen < Length(address!)) {
            let kept = LittleEndian(address![0..maxAddressLen - 1]);
            return Controlled XorEqualLookup(cs, (lvalue, table, kept));
        }

        // Drop inaccessible parts of table.
        let maxTableLen = 1 <<< Length(address!);
        if (maxTableLen < Length(table)) {
            let kept = table[0..maxTableLen-1];
            return Controlled XorEqualLookup(cs, (lvalue, kept, address));
        }

        // Base case: singleton table.
        if (Length(table) == 1) {
            XorEqualConst(address, ToBigInt(-1));
            Controlled XorEqualConst(cs + address!, (lvalue, table[0]));
            XorEqualConst(address, ToBigInt(-1));
            return ();
        }

        // Recursive case: divide and conquer.
        let highBit = address![Length(address!) - 1];
        let restAddress = LittleEndian(address![0..Length(address!) - 2]);
        let h = 1 <<< (Length(address!) - 1);
        let lowTable = table[0..h-1];
        let highTable = table[h..Length(table)-1];
        using (q = Qubit()) {
            // Store 'all(controls) and not highBit' in q.
            X(highBit);
            Controlled InitToggle(cs + [highBit], q);
            X(highBit);

            // Do lookup for half of table where highBit is 0.
            Controlled XorEqualLookup([q], (lvalue, lowTable, restAddress));

            // Flip q to storing 'all(controls) and highBit'.
            Controlled X(cs, q);

            // Do lookup for half of table where highBit is 1.
            Controlled XorEqualLookup([q], (lvalue, highTable, restAddress));

            // Eager uncompute 'q = all(controls) and highBit'.
            Controlled UncomputeToggle(cs + [highBit], q);
        }
    }
    controlled adjoint self;
}

1 Note: I'm an author

$\endgroup$
3
  • $\begingroup$ Thank you for the explanation, comments and references Craig! Would this be reasonable for higher numbers of bits in $x$, say 10 or 20? And if not, do you know if there are implementations for generic multi-bit values of $x$ that use things like polynomial approximations or any other technique as like that? $\endgroup$ Mar 25 at 20:53
  • 2
    $\begingroup$ @RajivKrishnakumar For 20 I'd probably do an interpolated lookup, and maybe try to extract factors of 2 to canonicalize the problem because factors of 2 can be handled by manual shifts. $\endgroup$ Mar 25 at 21:39
  • 2
    $\begingroup$ @RajivKrishnakumar You could also break $e^{x}$ into $e^{x_1 + x_2/2^5 + x_3 / 2^10 + x_4 / 2^15}$ where each $x_k$ value was a 5 qubit integer, separately look up each, and multiply them all together. $\endgroup$ Mar 30 at 23:14
1
$\begingroup$

This might not be the most ideal implementation but an interesting way you could approximate this is using $R_y$s and $QFT^{-1}$.

If we Taylor expand $e^x = 1 + x + \frac{x^2}{2!} ...$ we can use the polynomial amplitude encoding in https://static-content.springer.com/esm/art%3A10.1038%2Fs41534-019-0130-6/MediaObjects/41534_2019_130_MOESM1_ESM.pdf, Section D.

Using the example from the paper for a polynomial $p(x) = ax^2 + bx + c$, where we substitute our coefficients from the Taylor expansion, we can apply the controlled $R_y$s to an ancilla:

$ U_{e^x}|0\rangle = R_y(1.5)^{q_2}R_y(2)^{q_1,q_2}R_y(4)^{q_1}R_y(1)|0\rangle \rightarrow \cos(e^x/2)|0\rangle + \sin(e^x/2)|1\rangle$.

We can use take QFT of the ancilla to a register $|R\rangle$

$QFT^{-1}U_{e^x}|0\rangle|R\rangle \rightarrow U_{e^x}|0\rangle|\sin(e^x/2)\rangle$.

Finally we can use the approximation $\sin(x) \approx x$ assuming $x$ is sufficiently small. We can control this by scaling the Taylor approximation polynomial.

$QFT^{-1}U_{e^x}|0\rangle|R\rangle \rightarrow U_{e^x}|0\rangle|\sin(e^x/2)\rangle \approx U_{e^x}|0\rangle|e^x/2\rangle $

The main caveat is we need to ensure the correct scaling, with a constant $K$, ideally we would like our scaling s.t. $\sup Ke^x < \frac{\pi}{4}$ in our domain of $x$. As such we would obtain

$|Ke^x/2\rangle$,

and then we would need to have a circuit to descale. If we take $K$ in the form of $2^{-n}$, then in fact we don't need to implement a descaling circuit and we can just rescale the values of the coefficients of our binary representation by $2^{n+1}$ to recover our approximation to $e^x$.

Note: Here was are assuming $x$ is a binary integer.

$\endgroup$
1
$\begingroup$

Leaving this here. Recently published, might be useful for this question.

Efficient Evaluation of Exponential and Gaussian Functions on a Quantum Computer https://arxiv.org/abs/2110.05653

$\endgroup$
1
  • $\begingroup$ Just found this yesterday too! Thanks for posting it here :) $\endgroup$ Oct 14 at 15:54

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.