In this paper, we present Q# implementations for arbitrary single-variabled fixed-point arithmetic op-erations for a gate-based quantum computer based on lookup tables (LUTs). In general, this is an inefficent way of implementing a function since the number of inputs can be large or even infinite. However, if the input domain can be bounded and there can be some error tolerance in the output (both of which are often the case in practical use-cases), the quantum LUT implementation of certain quantum arithmetic functions can be more efficient than their corresponding reversible arithmetic implementations. We discuss the implementation of the LUT using Q# and its approximation errors. We then show examples of how to use the LUT to implement quantum arithmetic functions and compare the resources required for the implementation with the current state-of-the-art bespoke implementations of some commonly used arithmetic functions. The implementation of the LUT is designed for use by practitioners to use when implementing end-to-end quantum algorithms. In addition, given its well-defined approximation errors, the LUT implementation makes for a clear benchmark for evaluating the efficiency of bespoke quantum arithmetic circuits.In this paper, we present Q# implementations for arbitrary single-variabled fixed-point arithmetic op-erations for a gate-based quantum computer based on lookup tables (LUTs). In general, this is an inefficent way of implementing a function since the number of inputs can be large or even infinite. However, if the input domain can be bounded and there can be some error tolerance in the output (both of which are often the case in practical use-cases), the quantum LUT implementation of certain quantum arithmetic functions can be more efficient than their corresponding reversible arithmetic implementations. We discuss the implementation of the LUT using Q# and its approximation errors. We then show examples of how to use the LUT to implement quantum arithmetic functions and compare the resources required for the implementation with the current state-of-the-art bespoke implementations of some commonly used arithmetic functions. The implementation of the LUT is designed for use by practitioners to use when implementing end-to-end quantum algorithms. In addition, given its well-defined approximation errors, the LUT implementation makes for a clear benchmark for evaluating the efficiency of bespoke quantum arithmetic circuits.

arXiv:2210.11786IEEE/ACM International Workshop on Quantum Computing Software (QCS)Nov 1, 20223 citations

Pseudorandomness with Proof of Destruction and Applications

Amit Behera, Zvika Brakerski, Or Sattath +1 more

Lecture notes in computer scienceJan 1, 202310 citations

Square Table Lookup Multiparty Computation Protocol

Zhongqi Wang, Keita Fuse, Takashi Nishide

A secure interval test protocol is a powerful and useful tool to check whether a shared secret value is within a particular interval without revealing any information about the secret value, and therefore it has important applications in secure multi-party computation, machine learning, privacy-preserving location services, and many other areas. The secure inerval test protocol can be used as a building block in larger or more complex systems. A secure table lookup protocol based on the secure interval test can be used to implement approximate calculations of certain functions. In this work, we propose a square table lookup protocol based on the secure interval test protocol, which improves the efficiency in a certain setting compared to the state-of-the-art secure table lookup protocol proposed by Morita el al. (CANS'19). We reduce the computational complexity of the table lookup protocol from $O(N)$ to $O(\sqrt{N})$ where $N$ is the number of elements in the lookup table by changing the dimension of the lookup table from a one-dimensional array to a two-dimensional array, arranging it as a square matrix, and redesigning the procedure of secure table lookup protocol.A secure interval test protocol is a powerful and useful tool to check whether a shared secret value is within a particular interval without revealing any information about the secret value, and therefore it has important applications in secure multi-party computation, machine learning, privacy-preserving location services, and many other areas. The secure inerval test protocol can be used as a building block in larger or more complex systems. A secure table lookup protocol based on the secure interval test can be used to implement approximate calculations of certain functions. In this work, we propose a square table lookup protocol based on the secure interval test protocol, which improves the efficiency in a certain setting compared to the state-of-the-art secure table lookup protocol proposed by Morita el al. (CANS'19). We reduce the computational complexity of the table lookup protocol from$O(N)$to$O(\sqrt{N})$where$N$is the number of elements in the lookup table by changing the dimension of the lookup table from a one-dimensional array to a two-dimensional array, arranging it as a square matrix, and redesigning the procedure of secure table lookup protocol.

International Symposium on Computing and Networking Workshops (CANDARW)Nov 1, 20221 citation

O(N)

O(\sqrt{N})

where

N

is the number of elements in the lookup table by changing the dimension of the lookup table from a one-dimensional array to a two-dimensional array, arranging it as a square matrix, and redesigning the procedure of secure table lookup protocol.