SPRANGER MICHAEL (GB)
US20220188679A1 | 2022-06-16 | |||
EP22159844A | 2022-03-02 | |||
EP4053756A1 | 2022-09-07 | |||
US202217684254A | 2022-03-01 | |||
US20230036827A1 | 2023-02-02 |
SHOUVANIK CHAKRABARTI ET AL: "A Threshold for Quantum Advantage in Derivative Pricing", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 25 May 2021 (2021-05-25), XP081952474
BABU HAFIZ MD. HASAN ET AL: "Quantum Technology for Comparator Circuit", 2022 23RD INTERNATIONAL SYMPOSIUM ON QUALITY ELECTRONIC DESIGN (ISQED), 6 April 2022 (2022-04-06), pages 1 - 1, XP093089380, ISBN: 978-1-6654-9466-3, Retrieved from the Internet
A. MONTANARO: "Quantum speedup of monte carlo methods", PROCEEDINGS OF THE ROYAL SOCIETY A: MATHEMATICAL, PHYSICAL AND ENGINEERING SCIENCES, vol. 471, no. 2181, 2015, pages 20150301, XP055588515, Retrieved from the Internet
S. HERBERT, EVERY CLASSICAL SAMPLING CIRCUIT IS A QUANTUM SAMPLING CIRCUIT, 2021, Retrieved from the Internet
CLAIMS 1. A computer implemented method for generating a quantum circuit for use by a quantum computing apparatus to prepare a state therein that encodes a target multivariate probability distribution, wherein the method includes steps of: (i) receiving first input data defining a quantum circuit P for encoding the target probability distribution onto a state of one or more qubits; (ii) receiving second input data defining the number of one or more dimensions (d) of the target probability distribution; (iii) receiving third input data defining a number of one or more qubits corresponding to each dimension of the d dimensions of the target probability distribution; (iv) receiving fourth input data defining a support for each dimension of the d dimensions of the target probability distribution; (v) generating from the first, second, third, and fourth data an enhanced form of the quantum circuit; and (vi) outputting data defining the enhanced quantum circuit; wherein the sum of the numbers of qubits corresponding to each dimension is equal to the number of the one or more qubits of the state that the target probability distribution is encoded onto by circuit P, and wherein generating the enhanced quantum circuit in step (v) includes at least one of: (a) generating additional quantum circuitry for the quantum circuit based on the input data of steps (i)-(iv) to sum random variables of the target probability distribution and to encode the sum as a new dimension of the multivariate distribution; (b) generating additional quantum circuitry for the quantum circuit based on the input data of steps (i)-(iv) to calculate a product of a plurality of random variables of the target probability distribution and to encode the product as a new dimension of the multivariate distribution; (c) generating additional quantum circuitry for the quantum circuit based on the input data of steps (i)-(iv) to calculate at least one of a maximum and a minimum of two correlated random variables represented as dimensions of the multivariate distribution and to encode each of the at least one of the maximum and minimum as a new dimension of the multivariate distribution; or (d) generating additional threshold quantum circuitry for the quantum circuit based on the input data of step (i)-(iv) to check if a threshold condition is satisfied by a single random variable represented as one dimension of the multivariate distribution and to encode the result of the check on at least one extra truth qubit. 2. The method of claim 1, wherein step (d) of generating threshold quantum circuitry to check if a threshold condition is satisfied is performed for a plurality of different single random variables with a corresponding threshold condition and wherein step (v) of generating the enhanced quantum circuit further comprises: generating additional threshold quantum circuitry for the quantum circuit based on the input data of step (i)-(iv) to add at least one further flag qubit, wherein the at least one further flag qubit is computed from an exclusive sum of products (ESOP) of each truth value of a plurality subset of the plurality of extra truth qubits. 3. The method of claim 1 or 2, wherein the quantum circuit P is configured for implementing quantum Monte Carlo integration (QMCI). 4. The method of claim 1, 2, or 3, wherein there is a plurality of the dimensions (d). 5. The method of any preceding claim, wherein the summing in step (a) is implemented using a binary adder circuit. 6. The method of any preceding claim, wherein step (vi) also comprises outputting first additional data defining the number of dimensions of the enhanced multivariate distribution, including any new dimension of steps (a)-(d), and second additional data defining a number of one or more qubits corresponding to each dimension of the enhanced multivariate distribution, and third additional data defining a support for each dimension of the enhanced multivariate distribution. 7. A quantum computing apparatus configured to receive data defining the enhanced quantum circuit that is generated using the method of any one of claims 1 to 6 and to implement the received enhanced quantum circuit. 8. A system for generating quantum circuits, the system comprising: a memory; and a processor, wherein the processor is configured to perform the steps of : (i) receiving first input data defining a quantum circuit P for encoding the target probability distribution onto a state of one or more qubits; (ii) receiving second input data defining the number of one or more dimensions (d) of the target probability distribution; (iii) receiving third input data defining a number of one or more qubits corresponding to each dimension of the d dimensions of the target probability distribution; (iv) receiving fourth input data defining a support for each dimension of the d dimensions of the target probability distribution; (v) generating from the first, second, third, and fourth data an enhanced form of the quantum circuit; and (vi) outputting data defining the enhanced quantum circuit; wherein the sum of the numbers of qubits corresponding to each dimension is equal to the number of the one or more qubits of the state that the target probability distribution is encoded onto by circuit P, and wherein generating the enhanced quantum circuit in step (v) includes at least one of: (a) generating additional quantum circuitry for the quantum circuit based on the input data of steps (i)-(iv) to sum random variables of the target probability distribution and to encode the sum as a new dimension of the multivariate distribution; (b) generating additional quantum circuitry for the quantum circuit based on the input data of steps (i)-(iv) to calculate a product of a plurality of random variables of the target probability distribution and to encode the product as a new dimension of the multivariate distribution; (c) generating additional quantum circuitry for the quantum circuit based on the input data of steps (i)-(iv) to calculate at least one of a maximum and a minimum of two correlated random variables represented as dimensions of the multivariate distribution and to encode each of the at least one of the maximum and minimum as a new dimension of the multivariate distribution; or (d) generating additional threshold quantum circuitry for the quantum circuit based on the input data of step (i)-(iv) to check if a threshold condition is satisfied by a single random variable represented as one dimension of the multivariate distribution and to encode the result of the check on at least one extra truth qubit. 9. The system of claim 8, wherein step (d) of generating threshold quantum circuitry to check if a threshold condition is satisfied is performed for a plurality of different single random variables with a corresponding threshold condition and wherein step (v) of generating the enhanced quantum circuit further comprises: generating additional threshold quantum circuitry for the quantum circuit based on the input data of step (i)-(iv) to add at least one further flag qubit, wherein the at least one further flag qubit is computed from an exclusive sum of products (ESOP) of each truth value of a plurality subset of the plurality of extra truth qubits. 10. The system of claim 8 or 9 wherein the quantum circuit P is configured for implementing quantum Monte Carlo integration (QMCI). 11. The system of claim 8, 9 or 10, wherein there is a plurality of the dimensions (d). 12. The system of any of claims 8 to 11, wherein the additional quantum circuit includes a binary adder circuit for implementing summing in (a). 13. The system of any of claims 8 to 12, wherein step (vi) also comprises outputting first additional data defining the number of dimensions of the enhanced multivariate distribution, including any new dimension of steps (a)-(d), and second additional data defining a number of one or more qubits corresponding to each dimension of the enhanced multivariate distribution, and third additional data defining a support for each dimension of the enhanced multivariate distribution. 14. The system of any of claims 8 to 13 further comprising a quantum computing apparatus configured to receive from the processor the data defining the enhanced quantum circuit and to implement the enhanced quantum circuit based on the received data. 15. A software product that is executable upon the system of any one of claims 8 to 14, to implement the method of any one of claims 1 to 6. |
2.7 - Reversible sum A circuit to take two registers, and , of sizes and respectively (where we let for simplicity) and outputs their sum, denoted (which has To do this, we can use Toffoli and CNOT gates to perform ‘in-place’ reversible sums. Let be two numbers to be added (not necessarily using the same number of bits when represented in binary) to give The essential circuit for the case is then as illustrated in FIG.2. Once the corresponding wire (which only ever acts as control) and any gates operating on this wire will be omitted resulting in a quantum circuit as depicted in FIG.3. The full summation circuit is given by working in ascending and adding circuit blocks in turn. The output register is initially set to zero. See also section 2.13 Optimisations below. 2.8 - Reversible multiplication A circuit to take two registers and of sizes and respectively (where we le for simplicity) and outputs their multiplied value, denoted (which has The output registe is initially set to zero. To do this, we perform for each bit in dimension i the addition of the value in dimension j into the result register, conditioned on the value and shifted by the place of the bit in dimension i. We use Toffoli, CNOT and higher order controlled X gates to perform ‘in-place’ reversible sums, where each such gate is conditioned on the according qubit in the first register. The high level overview of the multiplication as conditional additions is shown in the circuit diagram as shown in FIG.3.1. Except for the addition of the first qubit, which is a conditioned copy operation, we cannot assume that the previously affected qubits of the result register start in the 0 state. Due to the carry occurring for an initially non-empty result register, the affected range of the result register in each step is one bit wider than the number of bits of the second register. The summation subcircuit can be implemented in more than one way, of which we present here two variations with different resource requirements. Note that in all the below circuit diagrams we always assume the additional control on a qubit of the dimension i to be given implicitly. This means that all depicted gates have an additional control on this qubit of dimension i, which is not shown. 2.9 - Summation with ancillas Since the result register will not be empty except for the addition associated with the first bit, we use ancillas in order to handle the carry in the binary addition. In order to minimise the number of ancillas, we reorder the registers so that Let and be two numbers to be multiplied to give For the addition of the first qubit of the dimension j, in which there is no previous carry qubit, the essential circuit is then as shown in FIG. 3.2 where l is the index of the qubit in dimension i, on which the above circuit is controlled. All the following qubit additions do have a previous carry. The resulting circuit is as shown in FIG.3.3. The carry of the last qubit to be added will be reassigned as the most significant qubit of the result so far (thus increasing the size of the register r by one qubit), and will not be uncomputed in the following. In order to be able to reuse the ancillas during the multiplication, as well as for subsequent operations, it is necessary to uncompute them. We do this in reversed order of the qubits of the first register, using the adjoint of the above addition circuits as part of the uncomputation circuits. For uncomputing carry qubits , , the resulting circuit is performed in order of decreasing k as shown in FIG.3.4. Finally, for uncomputing for which there is no previous carry. The resulting circuit is as shown in FIG.3.5. As per the original circuit, these summation blocks are performed in term for each qubit in the register, and at the end the result in the register r is the multiplied value as desired. 2.10 - Summation without ancillas Here we describe a variation of the summation that does not need ancilla qubits. However the involved gates are controlled by a potentially high number of qubits, resulting in deep circuits when expressed as more basic Toffoli and CNOT gates. For each qubit to be added first all carries are computed, starting from the most significant down to the least significant, into the result register. Only then the qubit is added with a CNOT gate acting on the according result qubit. The circuit for adding the kth qubit of dimension j, implicitly conditioned on the lth qubit of dimension i, is given by depicted in FIG.3.6. 2.11 - Reversible max / min determination The conditions and lead to the appropriate one of the compared random variables being copied into a newly created dimension of the multivariate distribution. In order for the condition to be encoded in a summation circuit, one of the two values has to be inverted with X gates. If the dimensions have an unequal number of qubits (without loss of generality we can assume as the dimensions can be switched accordingly), then the dimension with more qubits is inverted, so as to not lose the inversion of leading qubits. After the uncomputation of the summation, there will be free qubits which will take the greater/lesser of the two random variables as a result, depending on the control qubit The full circuit is depicted in FIG.4 where the result is and the value of the control qubit is Note that the summation circuit can be trivially inverted by reversing the order of the gates. The summation circuit and its inverse are the same as for the summation operation. The circuits PRE for preserving the control qubit are depicted in FIG.5 for and depicted in FIG.6 for The COPY circuit for calculating the minimum is as depicted in FIG.7 for the case the Toffoli gates connected to non-existing qubits are omitted. For calculating the maximum, the order of copying and is switched. See also section 2.13 Optimisations below. 2.12 - Reversible threshold determination The threshold circuit is similar to the circuits for calculation of the maximum or minimum of two random variables. The notable difference is that the second value is a fixed classical value and therefore not encoded in a quantum register. It is convenient to define the threshold value in the following way: • If the user specifies a lower-bound, this is taken as a strict inequality. The output will only be set to 1 if the value in the register strictly exceeds the threshold, and otherwise (if less than or equal) the output is 0. • If the user specifies an upper-bound, this is taken as an inequality that can be saturated, that is if the value in the register is less than or equal to the threshold then the output will be set to one; it will only be set to zero in the case that the upper-bound is strictly exceeded. The idea is to use the above summation blocks to determine if a specified threshold is breached. However, since the threshold is a classical number, it does not need to be put into a register. • Let the number being compared to the threshold be bit number. • The threshold is inputted as a pure number, let this be T, and the first step is to convert this into a binary string, t, according to the for the register in question. This binary string should be obtained by rounding T down. So when the binary string, t, is interpreted as a value according to then this value should be less than or equal to T. Concretely, and consequently • .We now obtain t' as the one’s complement of t according to: (note that here is a binary string of ones). t' is obtained classically. • t' is itself a binary string of bits. We now sum t' and to give an bit number, r. The most significant bit will be set exactly if this is equivalent to ^ > Note that with these conventions, the value yields a trivial condition, as the lower bound is never satisfied, whereas the upper bound always is. Useful threshold values are therefore To achieve the threshold calculation, we can use the summation logic above, but without putting t’ into a register. The full circuit is given by a quantum circuit as depicted in FIG.8 where the value of c is . For an upper bound, the resulting threshold control qubit c is inverted with an X gate. The circuits for adding an implicit binary digit are given by a quantum circuit as depicted in FIG.9, for and given by the quantum circuit depicted in FIG.10, for The most significant qubit of the result is the threshold control qubit. The other result qubits are “uncomputed” for reuse as ancillas. The uncomputation circuit is the reverse (adjoint) of the summation circuit, with a preservation circuit before that prevents the uncomputation of the threshold control qubit. The preservation circuits are similar to their counterparts in the Min-Max calculation, but with the second register omitted, since the threshold value is given implicitly. They are given by a quantum circuit as depicted in FIG.11, for and a quantum circuit as depicted in FIG.12, for denotes the threshold control qubit. . Note that the total number of ancillas needed is the maximum number of ancillas over all threshold blocks, since they can be reused. See also section 2.13 Optimisations below. 2.13 - Optimisations Various optimisations have been developed for the invention, as set out below. • If the thresholds are ordered in decreasing number of qubits then ancillas may be converted into controls of following thresholds. • Controlled operations at the beginning of a circuit can be removed if the incoming qubits are known to be in the 0 state. Examples of Reversible sum and Reversible threshold optimisation are described below. o Reversible sum optimisation: An example optimised circuit for use in a Reversible sum operation is shown in FIG. 17. In addition to the circuits described in the above section "Reversible sum" and shown in FIG.2 and FIG.3, the fact that the qubits holding the result are initially in the 0 state can be used in an optimisation. For the first addition step (k=1), the circuit of FIG.2 simplifies to that shown in FIG.17. o Reversible threshold optimisation Building on the Reversible sum optimisation described above, it is possible to further optimise the summation circuit in the Reversible threshold operation, taking into account that the incoming qubits are known to be in the 0 state. Moreover, since the classical threshold value t’ is known at the time of circuit construction, the operations without a preceding carry can comprise more than the first step. Starting from the least significant classical bit, for the first step and the following steps as long as the previous classical bit is 0, the previous addition cannot have yielded a carry. Then simplified versions of the circuits in FIG. 9 and FIG. 10 are used, which assume the previous carry to be 0. One simplified version for the classical bit t’ k = 0 is shown in FIG. 19.1. A second version, for the classical bit t’k = 1, is shown in FIG.19.2. • The conservation circuit can be merged with the adjoined summation circuit. o Reversible max/min optimisation: Instead of inserting a preserving circuit ("conservation circuit"), the most significant qubit can be prevented from uncomputation by changing the uncomputation circuit SUM ϯ and removing PRE from the circuit shown in FIG.4 This amounts to the merging of the conservation circuit with the adjoined summation circuit. The changed circuit SUMϯ will be similar to the previous circuit, but the first uncomputation step will be different. The uncomputation circuit is therefore no longer the adjoint operation to SUM. For Ni = Nj = Nd+1 − 1, the circuit of FIG.18.1 is used. For Ni > Nj, the circuit of FIG.18.2 is used. o Reversible threshold optimisation: As for the reversible max / min, also for the threshold the conservation circuit can be merged with the uncomputation circuit by changing the first uncomputation step. This amounts to a change of and removal of PRE from FIG.8. The first uncomputation step is replaced with one of the circuits of FIG.20.1 (for the classical bit where the classical bit is padded with 0) and 20.2 (for • If the same threshold value is used both as a lower and upper bound, then only one such threshold circuit is needed. • In the threshold circuit, the value can be inverted with X gates, instead of the threshold value t. This might lead to a lower usage of X gates, depending on the threshold value and possibly compiler optimisation. • For the maximum/minimum circuit, the dimension with fewer qubits can be inverted, and the leading 1s can be summed implicitly as in the threshold circuit. This might result in a lower number of X gates used, again also dependent on compiler optimisation. • In a threshold circuit only as many qubits as are needed as ancillas/controls/flag for the following threshold circuits need to be uncomputed. The summation in the last threshold circuit does not need to be uncomputed, since the ancillas are not used again. • One of the ancillas of the threshold circuit can be reused as the flag qubit of the ESOP circuit. • Combining the above two ideas, just a single qubit of the summation in the last threshold circuit can be uncomputed (while leaving the others) to be reused as the flag qubit of the ESOP circuit. • If the flag qubit is not set, a rotation around the Y axis by is performed. By moving this rotation including the X gates to the right of the other rotation gates, the final X gave can be removed, since the final value of the flag qubit is irrelevant. The multiplication of two dimensions can be easily extended to the case where the minimum points are not zero, but integer multiples of the respective spacing. Note that if then the product value of those two dimensions is ( . It follows that we get the desired result when the classical values are added to their respective dimension before the multiplication. Example This example showcases the above: • The Input is a circuit (that is, simply 5 Hadamard gates on 5 qubits), which is to be interpreted as a 3 dimensional probability distribution such that: o , have 2 qubits, o has 1 qubit. o For all, • Then we implement the following: o Create a new dimension: o Create a new dimension: o Threshold o Threshold o Flag true if: Threshold 1 xor Threshold 2 (note they cannot both we met, so xor has the same effect as or here) Input andoperations 2.14 - Enhanced circuit An enhanced circuit is depicted in FIG.13, wherein: 1. The initial uniform distribution of the first 3 dimensions is prepared 2. The random variables and are added into dimension 4 3. As the first step of calculating the maximum of and the latter is inverted 4. The random variables and the inverted are added into dimension 5, with taking the information which one is greater and wherein the enhanced circuit is further depicted in FIG.14, wherein: 5. The previous summation is uncomputed, leaving the control qubit unaffected. 6. The inversion is undone, and the greater value (according to the control qubit) is copied into dimension 5 and wherein the enhanced circuit is further depicted in FIG.15, wherein: 7. The first threshold is computed, with taking the result. The enhanced circuit is depicted in FIG.16, wherein: 8. The second threshold is computed, with taking the result. 9. The ESOP of is computed, with the flag qubit taking the result. 2.15 - Output state The output state is an equal superposition of 32 computational basis states, each represented as one line in the below output. The first tuple of each line contains the values of the 5 final dimensions, where the first 3 are the input, the fourth is the result of the summation, and the fifth is the result of the maximum calculation. The following tuple contains the 3 control qubits. The next number is the value of the 3 ancilla qubits, which is always 0. The final number is the flag qubit. Note that the values of the control qubits are inconsequential for the Monte Carlo Integration. The flag qubit indicates whether the ESOP threshold condition has been met.
2.16 – System Architecture Figure 21 is a schematic representation of a hybrid computing system 100 including a classical (binary) digital computing apparatus 110 and a quantum computing apparatus 210. Each of the classical computing system 110 and the quantum computing system 210 may comprise one or more computing devices. The classical computer system 110 includes non-volatile data storage 120, at least one volatile memory 130 and at least one processor 140. A Quantum Monte Carlo Integration (QMCI) engine 150 is implemented as a computer program product stored within the non-volatile storage 120 and executable by the processor 140 to carry out a method for generating quantum circuits according to the invention, and for controlling interactions with the quantum computing apparatus. This includes control software for transferring a generated quantum circuit to the quantum computing system for execution. In particular, the QMCI includes a circuit builder module that is adapted to generate an enhanced quantum circuit for execution on the quantum computing apparatus to implement a set of operations applied to the dimensions of probability distributions, including maximum/minimum determinations, sum, multiplication and threshold determinations. The circuit builder module is integrated with a library of standardised circuits for preparing univariate and multivariate probability distributions, including normal, log-normal, and binomial distributions. This can provide the above-referenced first input data defining a quantum circuit P for encoding the target probability distribution onto a state of one or more qubits. The circuit builder module adds selected operators as additional circuitry to the standardised circuits, to perform the computations required by a user. This enables generation of quantum circuits for efficiently estimating properties of modelled complex quantum systems. The steps of a method of generating a quantum circuit are shown in Figure 22. The circuit builder module of the QMCI engine runs on the classical computing apparatus 110 and configures the processor 140 to generate quantum circuitry for a set of required operations, performing the steps of : (i) receiving 300 first input data defining a quantum circuit P for encoding the target probability distribution onto a state of one or more qubits; (ii) receiving 310 second input data defining the number of one or more dimensions (d) of the target probability distribution; (iii) receiving 320 third input data defining a number of one or more qubits corresponding to each dimension of the d dimensions of the target probability distribution; (iv) receiving 330 fourth input data defining a support for each dimension of the d dimensions of the target probability distribution; (v) generating 340 from the first, second, third, and fourth data an enhanced form of the quantum circuit; and (vi) outputting 350 data defining the enhanced quantum circuit. As a further input to the computer system 100, user-defined instructions can specify required operations that can generate quantum circuitry, as described in detail above, to enhance a quantum state preparation circuit encoding some multivariate probability distribution, such that the circuit further includes dimensions pertaining to sums, products and maxima / minima of other dimensions, and optionally includes one or more further “flag” qubits that will act as conditional control in quantum Monte Carlo integration (QMCI). The enhanced quantum circuit 220 is then implemented on the quantum computing apparatus, mapping 360 the logical qubits of the generated quantum circuit onto physical qubits 230 of the quantum computing apparatus 210, and the quantum circuit is then executed by manipulating these physical qubits to perform calculations such as a sum, a product, determination of maxima / minima and evaluation of threshold conditions. The quantum circuit as implemented on the quantum computing apparatus can be considered as analogous to a compiled program (low-level code) which has been adapted to run on the specific hardware implementation of the quantum computer, with an implementation taking account of the number and connectivity of the qubits and gates of the quantum computing apparatus. The results of these quantum computer calculations are output 370 to the classical computer system for evaluating properties of a whatever physical system or computational system the user has chosen to evaluate. The results of this analysis are provided as an output from the computing system 100. References [Ref1] S. Herbert, "Quantum monte-carlo integration: The full advantage in minimal circuit depth," 2021. [Online]. Available: https://arxiv.org/abs/2105.09100 [Ref2] A. Montanaro, “Quantum speedup of monte carlo methods,” Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol.471, no.2181, p.20150301, 2015. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.2015 .0301 [Ref3] S. Herbert, "Every classical sampling circuit is a quantum sampling circuit," 2021. [Online]. Available: https://arxiv.org/abs/2109.04842
Next Patent: Tuning Stabilisers for Stringed Instrument