Next Article in Journal
A Non-Stochastic Special Model of Risk Based on Radon Transform
Next Article in Special Issue
The Thermodynamics of the Van Der Waals Black Hole Within Kaniadakis Entropy
Previous Article in Journal
Text-Enhanced Graph Attention Hashing for Cross-Modal Retrieval
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Prepare Linear Distributions with Quantum Arithmetic Units

Department of Physics, College of Science, Northeastern University, Shenyang 110819, China
Entropy 2024, 26(11), 912; https://doi.org/10.3390/e26110912
Submission received: 23 September 2024 / Revised: 24 October 2024 / Accepted: 25 October 2024 / Published: 28 October 2024
(This article belongs to the Special Issue Entropy in Classical and Quantum Information Theory with Applications)

Abstract

:
Quantum arithmetic logic units (QALUs) perform essential arithmetic operations within a quantum framework, serving as the building blocks for more complex computations and algorithms in quantum computing. In this paper, we present an approach to prepare linear probability distributions with quantum full adders. There are three main steps. Firstly, Hadamard gates are applied to the two input terms, preparing them at quantum states corresponding to uniform distribution. Next, the two input terms are summed up by applying quantum full adder, and the output sum is treated as a signed integer under two’s complement representation. By the end, additional phase 1 is introduced to the negative components. Additionally, we can discard either the positive or negative components with the assistance of the Repeat-Until-Success process. Our work demonstrates a viable approach to prepare linear probability distributions with quantum adders. The resulting state can serve as an intermediate step for subsequent quantum operations.

1. Introduction

Quantum computing signifies a transformative shift in the landscape of computational capabilities, which introduces a level of computational power that enables the efficient resolution of problems deemed intractable by classical computing paradigms [1,2,3,4,5,6,7,8,9,10,11,12,13]. Quantum arithmetic logic units (QALUs) constitute the centerstone of quantum computing. In classical computing, the elementary arithmetic logic units (ALUs) are designed to execute basic arithmetic operations. Similarly, a variety of QALUs, such as quantum adders, subtractors, and multipliers, serve as the building blocks for more complicated algorithms in quantum computing. The best known example is Shor’s algorithm [14,15], where the quantum modular arithmetic plays a vital role.
Among various QALUs, the quantum adder plays a pivotal role, representing a fundamental operation integral to the execution of all algorithms that are constructed upon it. The first quantum adder was proposed in 1996, when Vedral and coworkers explicitly constructed the first quantum ripple carry adder [16], which is a significant landmark in the development of QALUs. Since then, a variety of quantum adders has been developed, including ripple carry [16,17,18], carry lookahead [19,20], carry save [21], and hybrid [22,23] structures. On the other hand, quantum adders can also be implemented based on quantum Fourier transform (QFT) [24,25]. QFT-based quantum adders [26,27] typically commence with a QFT block that converts the input state to the frequency domain, performs addition using controlled phase gates, and then reverts the state to the original domain through an inverse Fourier transform [28,29]. Moreover, recently, a novel approach was proposed to prepare arbitrary normal distributions in quantum registers, utilizing the QFT-based quantum adders [30].
In this paper, we revisit the fundamental quantum binary adders and propose a practical method for generating a linear probability distribution utilizing quantum adders. The following sections are organized as follows. In Section 2, we revisit the simple implementation of quantum binary adders, and demonstrate the outputs of iterative additions that sum up several standalone uniform superposition states. Next, in Section 3, we present how to prepare the linear probability distribution with quantum full adders in the two’s complement representation. By the end, the discussions and conclusions are present in Section 4.

2. Materials and Methods

Like classical binary adders, quantum binary adders add up two given terms, and return the output sum. In Figure 1, we depict the diagram of a typical quantum binary adder. The box colored in blue represents a quantum binary adder, and the inputs are given on the left side, whereas the outputs on the right side. There are 2 N qubits initialized at state | a N 1 a 0 and | b N 1 b 0 , representing the input binary numbers ( a N 1 a 0 ) b i n and ( b N 1 b 0 ) b i n . One qubit is initialized at state | 0 , representing the input carry (in general, the input carry is set as 0). There are N qubits all initialized at state | 0 to store the output sum. Generally, the quantum binary adders do not change the state of the inputs, and the output sum, a N + 1 digit binary number, is stored in the other N + 1 qubits (including the qubit that represents the input carry). As depicted in Figure 1a, the N + 1 qubits, which are prepared at | 0 at the beginning, are converted to state | s N s 0 after applying the quantum binary adder. The output state represents the output sum ( s N s 0 ) b i n , and we have
( s N s 0 ) b i n = ( a N 1 a 0 ) b i n + ( b N 1 b 0 ) b i n
For clarity, here, subscript b i n indicates that the number is binary.
In classical electronics, a cascade of one-bit full adders constitutes the simplest adder supporting multiple bits. The one-bit full adder adds three inputs [31]: two binary digits denoted as a and b, along with an input carry denoted as c i n . Then, the one-bit full adder produces two outputs: the sum s and output carry c o u t . The one-bit full adder performs binary addition as
s = a b c i n
c o u t = ( a · b ) + ( c i n · ( a b ) )
where a , b , c i n , c o u t , s = 0 , 1 , and a + b + c i n = s + 2 c o u t . Similarly, the quantum one-bit full adder, denoted as U + , performs binary addition as
U + | a , b , c i n , 0 = | a , b , s , c o u t
where the outputs s, c o u t are as given in Equations (2) and (3). In Figure 2b, we present the circuit of a typical quantum one-bit full adder, which is formed by two Toffoli gates along with three CNOT gates. There are four qubits involved in operation U + , two qubits represent the input terms a and b, one qubit represents the input carry c i n and stores the output sum s, and the last qubit initialized at state | 0 stores the output carry c o u t .
The simplest quantum adder that supports multiple bits can be formed by cascading multiple one-bit full adders. Figure 2a is a schematic diagram of three cascade quantum one-bit full adders, where the blue boxes indicate operation U + , with inputs on the left side and outputs on the right side. The addition starts from the least significant bits (LSBs) a 0 and b 0 , and the first operation U + is applied on the corresponding qubits. The output sum s 0 of the LSB addition is also the LSB of the output sum, whereas the output carry is sent to the addition of the next digit, a 1 and b 1 . In brief, the output carry performs as the input carry in the addition of the next digit, and the output carry of the most significant bit (MSB) is just the MSB of the output sum.
In general, we can sum up M standalone input terms by applying M 1 quantum adders that support multiple bits. Figure 1a is a schematic diagram of summing up three input terms with two quantum adders. At the beginning, all qubits are initialized at state | 0 , and the inputs are prepared at uniform superposition by applying Hadamard gates. Qubits denoted as q A , q B , q C , and q S are involved in the first addition. The output sum is then sent to the succeeding addition, along with qubits Q B , Q C , and Q S . The superscripts indicate that the qubits represent the input terms ( A , B ), the input carry (C), or the output sum (S). After adding up M standalone input terms, the output quantum state, denoted as Φ M , can be given as
Φ M = 1 2 N M m = 1 M a m = 0 2 N 1 | a m | m = 1 M a m
The M input terms are denoted as a m , m = 1 , 2 , , M . As all inputs are N bit binary unsigned integers, a m ranges from 0 to 2 N 1 . Then, we measure the qubits that represent the output sum, and denote the probability of obtaining result x as P r ( x ) , where for simplicity, we denote the sum as an integer x, and the standard quantum state of the output sum corresponds to the binary form of x. The theoretical prediction of P r ( x ) for various M and N are as depicted in Figure 2c–n, where there are in total M input terms, and each input is a N bit binary number. As N and M increase, the distribution P r ( x ) begins to resemble a normal distribution. Thus, it is a feasible approach to prepare normal distribution with quantum adders! [30] (In Ref. [30], Rattew and coworkers proposed a quantum algorithm for the efficient preparation of arbitrary normal distributions, utilizing the quantum random work, and quantum Fourier Transformations or quantum adders, along with Mid-Circuit Measurement and Reuse (MCMR) techniques. The quantum algorithm can be implemented with a polynomial-depth circuit. Later, in Section 3, we show that our approach can prepare normal distributions also with polynomial-depth quantum circuits.).

3. Results

Here, we concentrate on the case M = 2 , where there are only two input terms. As both the inputs are N digit unsigned integers, the output sum is a N + 1 digit binary number. Recalling Equation (5), the overall quantum state after the addition (the input carry c i n = 0 ) can be written as
Φ M = 2 = 1 2 N a = 0 2 N 1 b = 0 2 N 1 | a | b | a + b
where the two input terms are denoted as a and b, and we have a , b 2 N 1 , whereas the output sum, for simplicity denoted as x, ranges from 0 to 2 N + 1 2 . Then, we measure the qubits corresponding to the sum after the addition, and denote P r ( x ) as the probability of obtaining result x. For 0 x 2 N 1 , there are in total x + 1 pairs of inputs a , b that lead to output sum x: a = 0 , b = x ; a = 1 , b = x 1 ; ⋯ and a = x , b = 0 . Similarly, for 2 N x 2 N + 1 2 , there are 2 N + 1 x 1 pairs of inputs a , b that lead to output sum x: a = 2 N 1 , b = x 2 N + 1 ; a = 2 N 2 , b = x 2 N + 2 ; ⋯ and a = x 2 N + 1 , b = 2 N 1 . Therefore, the probability of obtaining result x can be given as
P r ( x | c i n = 0 ) = 1 4 N ( x + 1 ) , 0 x 2 N 1 1 4 N ( 2 N + 1 x 1 ) , 2 N x 2 N + 1 2
P r ( x ) reaches to the peak at x = 2 N 1 , and P r ( 2 N 1 ) = 1 2 N . The theoretical predictions of P r ( x ) with M = 2 are as depicted in Figure 2c,g,k, where the distribution P r ( x ) is shaped like an isosceles triangle.
Till now, the output sum has been treated as a N + 1 digit unsigned integer. Hereafter, we will demonstrate that the distribution P r ( x ) can be converted to a linear distribution with two’s complement representation. Two’s complement is the most common method of representing signed integers in classical computers [31,32]. In two’s complement representation, the value χ of a N + 1 bit integer ( x N , x N 1 x 0 ) b i n is given as
χ = 2 N x N + j = 0 N 1 2 j x j
where x N is the sign bit indicating the sign, x N = 0 for non-negative integers, and x N = 1 for negative integers. The two’s complement representation of a non-negative number is just its ordinary binary representation, with sign bit 0.
In two’s complement representation, the N + 1 digit binary number ( x N x N 1 x 0 ) is treated as a signed integer. For 0 x 2 N 1 , we have x N = 0 , and the readout χ is still x. On the other hand, for 2 N x 2 N + 1 2 , we have x N = 1 , and the readout χ is negative. Recalling that x = j = 0 N 2 N x j , where x is the value of the unsigned binary integer ( x N x 0 ) b i n , we have
χ = x 2 N + 1 , 2 N x 2 N + 1 2
Thus, we can rewrite Equation (7) in two’s complement representation,
P r ( χ | c i n = 0 ) = 1 4 N χ + 1 , 2 N χ 2 N 1
Consider a simple example, the addition of two 3-digit unsigned binary numbers. In Table 1, we present the output sums for all possible inputs. For each input pairs, there are four components in Table 1. The first component (from top) is the output quantum state, where the input carry c i n is 0, and the second component is the corresponding readout of the sum (unsigned/signed). The other two components correspond to the case where c i n = 1 , and will be discussed later. For example, consider the addition of | 100 and | 101 . With input carry c i n = 0 , the output quantum state is | 1001 . If we treat the 4-digit binary number ( 1001 ) b i n as an unsigned integer, then the readout is 1 × 2 3 + 0 × 2 2 + 0 × 2 1 + 1 × 2 0 = 9 . However, if we treat ( 1001 ) b i n as a signed integer in two’s complement representation, then the readout will be 1 × 2 3 + 0 × 2 2 + 0 × 2 1 + 1 × 2 0 = 7 .
In Figure 3, a straightforward demonstration of the addition is present. The quantum circuit is as depicted in Figure 3a, where q A and q B represent the input terms, q C represents the input carry, and the output sum is stored in q S . Initially, all qubits are prepared at state | 0 . Hadamard gates are then applied on qubits q A and q B , preparing them at uniform superpositions as depicted in Figure 3c,d. Here, in c i n = 0 , the operations in the dashed boxes are not applied. Then, the standard quantum adder is applied, summing the input terms, and the qubits q S are measured. If we treat the output sum as an unsigned integer, then the distribution P r ( x ) is as depicted in Figure 3e, which is shaped as an isosceles triangle, similar to Figure 2c,g,k. On the other side, if we treat the output sum as a signed integer in two’s complement representation, then we will obtain the distribution as shown in Figure 3g, which is a linear distribution according to Equation (10).
Notice that in Figure 3g, the probability of obtaining result 1 is zero. Sometimes, we prefer to have the zero probability at 0, in other words, setting P r ( χ = 0 ) = 0 . For this case, we can set the input carry c i n = 1 . In this context, the sum is a + b + 1 , where 1 is the input carry. Equation (7) can then be rewritten as
P r ( x | c i n = 0 ) = 1 4 N x , 1 x 2 N 1 1 4 N ( 2 N + 1 x ) , 2 N x 2 N + 1 1
The corresponding probability distribution is depicted in Figure 2f. If we treat the output as a signed integer in two’s complement representation, we have
P r ( χ | c i n = 0 ) = 1 4 N χ , 2 N χ 2 N 1
The output sums for c i n = 1 are also given in Table 1, where the third component is the output sum with input carry 1, and the last one is the corresponding readout (unsigned/signed). In Figure 2h, the distribution of the probability of obtaining various results after measuring the output sums is depicted, where the output sum is treated as signed integers in two’s complement representation. By this mean, the probability of obtaining result 0 is zero as shown in Figure 2h.
Although the probability is always non-negative, we can also introduce an additional phase to the negative components. As shown in Figure 2b, we can apply a Pauli-Z operation on the qubit q N S after applying the quantum adder. The qubit q N S represents the MSB of the output sum and is the sign bit if we treat the sum as a signed integer in two’s complement representation. Recalling Equation (8), for negative components, the sign bit is 1; otherwise, the sign bit is 0. Thus, the Pauli-Z operation can introduce an additional phase 1 to the negative components.
Furthermore, we can also discard either the positive or negative components with the assistance of the Repeat-Until-Success process [33,34,35]. After applying the quantum adder, we can measure the qubit q N S . If we obtain result | 1 , then the distribution probability is ( c i n = 1 )
P r ( χ | c i n = 1 ) = 1 ( 1 + 2 N ) 2 N 1 χ , 2 N χ 0
Otherwise, if we obtain result | 0 , the distribution probability is
P r + ( χ | c i n = 1 ) = 1 ( 2 N 1 ) 2 N 1 χ , 0 χ 2 N 1
where the subscripts ± indicate the measurement results. If we want to obtain a linear probability distribution for the negative range as shown in Equation (13), then we need to repeat the whole process until we obtain result | 1 when measuring the qubit q N S . On the contrary, if we prefer to obtain the probability distribution for the positive range as shown in Equation (14), then we need to repeat until we obtain result | 0 .
The time complexity of the proposed approach is mainly determined by the quantum adder. Generally, the time complexity of a typical N bit binary quantum adder, as depicted in Figure 2b, is of the O ( N ) order, where there are 2 N Toffoli gates along with 3 N CNOT gates. However, due to the limited connectivity, it can be challenging to implement large quantities of Toffoli gates on the quantum computers in NISQ era. To address this issue, we propose an alternative design of quantum binary adders in our recent work [36], utilizing only Pauli-X gates, CNOT gates, and C X (CSX) gates, and all two-qubit gates are operated between nearest neighbor qubits. The time complexity of the quantum adder is still of the O ( N ) order. Therefore, to prepare the linear distribution as shown in Equation (12), the time complexity is O ( N ) . Furthermore, the proposed approach can be extended to prepare normal distributions as depicted in Figure 2c–n. Theoretically, the time complexity of summing up M independent uniform superposition states is O ( ( M 1 ) N ) . In other words, the proposed approach can be implementable with a polynomial-depth circuit.

4. Discussion

In this paper, we revisit the elementary quantum binary adders, and propose a viable approach to prepare linear probability distribution with the quantum adders. There are three main steps to obtain the linear probability distribution. Initially, Hadamard gates are applied to the input qubits, transforming them into uniform superposition states. Following this, the input qubits are processed through a quantum full adder, where their sum is computed, and the resulting output is interpreted as a signed integer in two’s complement representation. At a subsequent stage, a phase shift of 1 is introduced to the components representing negative values. Furthermore, the positive or negative components may be selectively discarded using a Repeat-Until-Success protocol. The resulting output can serve as an intermediate state for succeeding quantum operations.

Funding

This research was funded by National Natural Science Foundation of China (NSFC) under Grant No. 12305012.

Institutional Review Board Statement

Not applicable.

Data Availability Statement

All data and materials supporting the results or analyses presented in this paper are available from the corresponding author upon reasonable request.

Conflicts of Interest

The author declares no conflicts of interest.

References

  1. Lloyd, S. Universal quantum simulators. Science 1996, 273, 1073–1078. [Google Scholar] [CrossRef] [PubMed]
  2. Biamonte, J.; Wittek, P.; Pancotti, N.; Rebentrost, P.; Wiebe, N.; Lloyd, S. Quantum machine learning. Nature 2017, 549, 195–202. [Google Scholar] [CrossRef] [PubMed]
  3. Preskill, J. Quantum computing in the NISQ era and beyond. Quantum 2018, 2, 79. [Google Scholar] [CrossRef]
  4. Li, Z.; Liu, X.; Wang, H.; Ashhab, S.; Cui, J.; Chen, H.; Peng, X.; Du, J. Quantum simulation of resonant transitions for solving the eigenproblem of an effective water Hamiltonian. Phys. Rev. Lett. 2019, 122, 090504. [Google Scholar] [CrossRef]
  5. Cao, Y.; Romero, J.; Olson, J.P.; Degroote, M.; Johnson, P.D.; Kieferová, M.; Kivlichan, I.D.; Menke, T.; Peropadre, B.; Sawaya, N.P.; et al. Quantum chemistry in the age of quantum computing. Chem. Rev. 2019, 119, 10856–10915. [Google Scholar] [CrossRef]
  6. Google AI Quantum and Collaborators; Arute, F.; Arya, K.; Babbush, R.; Bacon, D.; Bardin, J.C.; Barends, R.; Boixo, S.; Broughton, M.; Buckley, B.B.; et al. Hartree-Fock on a superconducting qubit quantum computer. Science 2020, 369, 1084–1089. [Google Scholar]
  7. Li, J.; Kais, S. Quantum cluster algorithm for data classification. Mater. Theory 2021, 5, 6. [Google Scholar] [CrossRef]
  8. Huang, H.Y.; Broughton, M.; Mohseni, M.; Babbush, R.; Boixo, S.; Neven, H.; McClean, J.R. Power of data in quantum machine learning. Nat. Commun. 2021, 12, 2631. [Google Scholar] [CrossRef]
  9. Altman, E.; Brown, K.R.; Carleo, G.; Carr, L.D.; Demler, E.; Chin, C.; DeMarco, B.; Economou, S.E.; Eriksson, M.A.; Fu, K.M.C.; et al. Quantum simulators: Architectures and opportunities. PRX Quantum 2021, 2, 017003. [Google Scholar] [CrossRef]
  10. Schlimgen, A.W.; Head-Marsden, K.; Sager, L.M.; Narang, P.; Mazziotti, D.A. Quantum simulation of open quantum systems using a unitary decomposition of operators. Phys. Rev. Lett. 2021, 127, 270503. [Google Scholar] [CrossRef]
  11. Sajjan, M.; Li, J.; Selvarajan, R.; Sureshbabu, S.H.; Kale, S.S.; Gupta, R.; Singh, V.; Kais, S. Quantum machine learning for chemistry and physics. Chem. Soc. Rev. 2022, 51, 6475–6573. [Google Scholar] [CrossRef] [PubMed]
  12. Li, J.; Gao, X.; Sajjan, M.; Su, J.H.; Li, Z.K.; Kais, S. Møller-Plesset Perturbation Theory Calculations on Quantum Devices. arXiv 2023, arXiv:2308.01559. [Google Scholar]
  13. Ma, H.; Liu, J.; Shang, H.; Fan, Y.; Li, Z.; Yang, J. Multiscale quantum algorithms for quantum chemistry. Chem. Sci. 2023, 14, 3190–3205. [Google Scholar] [CrossRef] [PubMed]
  14. Shor, P.W. Algorithms for quantum computation: Discrete logarithms and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 20–22 November 1994; pp. 124–134. [Google Scholar]
  15. Ekert, A.; Jozsa, R. Quantum computation and Shor’s factoring algorithm. Rev. Mod. Phys. 1996, 68, 733. [Google Scholar] [CrossRef]
  16. Vedral, V.; Barenco, A.; Ekert, A. Quantum networks for elementary arithmetic operations. Phys. Rev. A 1996, 54, 147. [Google Scholar] [CrossRef]
  17. Cuccaro, S.A.; Draper, T.G.; Kutin, S.A.; Moulton, D.P. A new quantum ripple-carry addition circuit. arXiv 2004, arXiv:quant-ph/0410184. [Google Scholar]
  18. Gidney, C. Halving the cost of quantum addition. Quantum 2018, 2, 74. [Google Scholar] [CrossRef]
  19. Draper, T.G.; Kutin, S.A.; Rains, E.M.; Svore, K.M. A logarithmic-depth quantum carry-lookahead adder. arXiv 2004, arXiv:quant-ph/0406142. [Google Scholar] [CrossRef]
  20. Wang, S.; Chattopadhyay, A. Reducing depth of quantum adder using ling structure. In Proceedings of the 2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration (VLSI-SoC), Dubai, United Arab Emirates, 16–18 October 2023; pp. 1–6. [Google Scholar]
  21. Gossett, P. Quantum carry-save arithmetic. arXiv 1998, arXiv:quant-ph/9808061. [Google Scholar]
  22. Takahashi, Y.; Kunihiro, N. A fast quantum circuit for addition with few qubits. Quantum Inf. Comput. 2008, 8, 636–649. [Google Scholar] [CrossRef]
  23. Takahashi, Y.; Tani, S.; Kunihiro, N. Quantum addition circuits and unbounded fan-out. arXiv 2009, arXiv:0910.2530. [Google Scholar] [CrossRef]
  24. Weinstein, Y.S.; Pravia, M.; Fortunato, E.; Lloyd, S.; Cory, D.G. Implementation of the quantum Fourier transform. Phys. Rev. Lett. 2001, 86, 1889. [Google Scholar] [CrossRef]
  25. Coppersmith, D. An approximate Fourier transform useful in quantum factoring. arXiv 2002, arXiv:quant-ph/0201067. [Google Scholar]
  26. Draper, T.G. Addition on a quantum computer. arXiv 2000, arXiv:quant-ph/0008033. [Google Scholar]
  27. Cheng, K.W.; Tseng, C.C. Quantum full adder and subtractor. Electron. Lett. 2002, 38, 1343–1344. [Google Scholar] [CrossRef]
  28. Ruiz-Perez, L.; Garcia-Escartin, J.C. Quantum arithmetic with the quantum Fourier transform. Quantum Inf. Process. 2017, 16, 1–14. [Google Scholar] [CrossRef]
  29. Orts, F.; Ortega, G.; Combarro, E.F.; Garzón, E.M. A review on reversible quantum adders. J. Netw. Comput. Appl. 2020, 170, 102810. [Google Scholar] [CrossRef]
  30. Rattew, A.G.; Sun, Y.; Minssen, P.; Pistoia, M. The efficient preparation of normal distributions in quantum registers. Quantum 2021, 5, 609. [Google Scholar] [CrossRef]
  31. Horowitz, P.; Hill, W.; Robinson, I. The Art of Electronics; Cambridge University Press: Cambridge, UK, 1989; Volume 2. [Google Scholar]
  32. Burks, A.W.; Goldstine, H.H.; Von Neumann, J. Preliminary discussion of the logical design of an electronic computing instrument. In The Origins of Digital Computers: Selected Papers; Springer: Berlin/Heidelberg, Germany, 1946; pp. 399–413. [Google Scholar]
  33. Lim, Y.L.; Beige, A.; Kwek, L.C. Repeat-until-success linear optics distributed quantum computing. Phys. Rev. Lett. 2005, 95, 030505. [Google Scholar] [CrossRef]
  34. Wiebe, N.; Roetteler, M. Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits. arXiv 2014, arXiv:1406.2040. [Google Scholar] [CrossRef]
  35. Bocharov, A.; Roetteler, M.; Svore, K.M. Efficient synthesis of universal repeat-until-success quantum circuits. Phys. Rev. Lett. 2015, 114, 080502. [Google Scholar] [CrossRef] [PubMed]
  36. Li, J. Elementary Quantum Arithmetic Logic Units for Near-Term Quantum Computers. arXiv 2024, arXiv:2408.06561. [Google Scholar]
Figure 1. (a) Schematic diagram of quantum adder supporting multiple bits. The box colored in blue represents a quantum binary adder, and the inputs are given on the left side, whereas the outputs are on the right side. (b) Schematic diagram of summing up three input terms with two quantum adders. At the beginning, all qubits are initialized at state | 0 , and the inputs are prepared at uniform superposition by applying Hadamard gates. Qubits denoted as q A , q B , q C , q S are involved in the first addition. The output sum is then sent to the succeeding addition, along with qubits Q B , Q C , and Q S . The superscripts indicate that the qubits represent the input terms ( A , B ), the input carry (C), or the output sum (S).
Figure 1. (a) Schematic diagram of quantum adder supporting multiple bits. The box colored in blue represents a quantum binary adder, and the inputs are given on the left side, whereas the outputs are on the right side. (b) Schematic diagram of summing up three input terms with two quantum adders. At the beginning, all qubits are initialized at state | 0 , and the inputs are prepared at uniform superposition by applying Hadamard gates. Qubits denoted as q A , q B , q C , q S are involved in the first addition. The output sum is then sent to the succeeding addition, along with qubits Q B , Q C , and Q S . The superscripts indicate that the qubits represent the input terms ( A , B ), the input carry (C), or the output sum (S).
Entropy 26 00912 g001
Figure 2. (a) Schematic diagram of summing up three input terms with two quantum adders. (b) A typical implementation of quantum one-bit full adder. There are in total three CNOT gates and two Toffoli gates. (cn) The theoretical prediction of the output sum, where the input terms are M standalone uniform superpositions prepared by Hadamard gates. Each input term represents a N digit unsigned binary number. P r ( x ) is the probability of obtaining result x, where we denote the sum as an integer x, and the standard quantum state of the output sum corresponds to the binary form of x.
Figure 2. (a) Schematic diagram of summing up three input terms with two quantum adders. (b) A typical implementation of quantum one-bit full adder. There are in total three CNOT gates and two Toffoli gates. (cn) The theoretical prediction of the output sum, where the input terms are M standalone uniform superpositions prepared by Hadamard gates. Each input term represents a N digit unsigned binary number. P r ( x ) is the probability of obtaining result x, where we denote the sum as an integer x, and the standard quantum state of the output sum corresponds to the binary form of x.
Entropy 26 00912 g002
Figure 3. (a) Schematic diagram of the quantum circuit that sums up the two uniform superpositions, where q A and q B represent the input terms, q C is the input carry, and the output sum is stored in q S . The operations in dashed boxes are applied for c i n = 1 . (b) To introduce phase 1 to the negative components, we can apply a Pauli-Z gate on q N S , which represents the sign bit of the output. (c,d) Visualization of the uniform superpositions after applying Hadamard gates. (e,f) Distribution of the probability of obtaining various results after measuring the output sums, which is treated as unsigned integers. (g,h) Distribution of the probability of obtaining various results after measuring the output sums, which is treated as signed integers in two’s complement representation. In (e,g) we set the input carry c i n = 0 , whereas in (f,h) c i n = 1 .
Figure 3. (a) Schematic diagram of the quantum circuit that sums up the two uniform superpositions, where q A and q B represent the input terms, q C is the input carry, and the output sum is stored in q S . The operations in dashed boxes are applied for c i n = 1 . (b) To introduce phase 1 to the negative components, we can apply a Pauli-Z gate on q N S , which represents the sign bit of the output. (c,d) Visualization of the uniform superpositions after applying Hadamard gates. (e,f) Distribution of the probability of obtaining various results after measuring the output sums, which is treated as unsigned integers. (g,h) Distribution of the probability of obtaining various results after measuring the output sums, which is treated as signed integers in two’s complement representation. In (e,g) we set the input carry c i n = 0 , whereas in (f,h) c i n = 1 .
Entropy 26 00912 g003
Table 1. Table of the output sums, where both the input terms are 3-bit binary unsigned integers, and the input carry is set either 0 or 1. There are four components in each entry. From top to bottom, the first one is the output sum with input carry 0, and the second one is the corresponding readout (unsigned/signed), whereas the third component is the output sum with input carry 1, and the last one is the corresponding readout (unsigned/signed).
Table 1. Table of the output sums, where both the input terms are 3-bit binary unsigned integers, and the input carry is set either 0 or 1. There are four components in each entry. From top to bottom, the first one is the output sum with input carry 0, and the second one is the corresponding readout (unsigned/signed), whereas the third component is the output sum with input carry 1, and the last one is the corresponding readout (unsigned/signed).
Inputs | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111
| 000 | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111
0/01/12/23/34/45/56/67/7
| 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000
1/12/23/34/45/56/67/78/−8
| 001 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000
1/12/23/34/45/56/67/78/−8
| 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001
2/23/34/45/56/67/78/−89/−7
| 010 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001
2/23/34/45/56/67/78/−89/−7
| 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010
3/34/45/56/67/78/−89/−710/−6
| 011 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010
3/34/45/56/67/78/−89/−710/−6
| 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011
4/45/56/67/78/−89/−710/−611/−5
| 100 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011
4/45/56/67/78/−89/−710/−611/−5
| 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100
5/56/67/78/−89/−710/−611/−512/−4
| 101 | 0101 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100
5/56/67/78/−89/−710/−611/−512/−4
| 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101
6/67/78/−89/−710/−611/−512/−413/−3
| 110 | 0110 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101
6/67/78/−89/−710/−611/−512/−413/−3
| 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110
7/78/−89/−710/−611/−512/−413/−314/−2
| 111 | 0111 | 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110
7/78/−89/−710/−611/−512/−413/−314/−2
| 1000 | 1001 | 1010 | 1011 | 1100 | 1101 | 1110 | 1111
8/−89/−710/−611/−512/−413/−314/−215/−1
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

Li, J. Prepare Linear Distributions with Quantum Arithmetic Units. Entropy 2024, 26, 912. https://doi.org/10.3390/e26110912

AMA Style

Li J. Prepare Linear Distributions with Quantum Arithmetic Units. Entropy. 2024; 26(11):912. https://doi.org/10.3390/e26110912

Chicago/Turabian Style

Li, Junxu. 2024. "Prepare Linear Distributions with Quantum Arithmetic Units" Entropy 26, no. 11: 912. https://doi.org/10.3390/e26110912

APA Style

Li, J. (2024). Prepare Linear Distributions with Quantum Arithmetic Units. Entropy, 26(11), 912. https://doi.org/10.3390/e26110912

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop