Interval testing with reduced complexity
A method for compiling executable code for execution on a computer includes: (a) receiving source code instructing the computer to execute an interval test to determine whether an interval defined by integers a and b encloses an integer x; (b) decomposing the interval test into a first comparison between the integer a and the integer x and a second comparison between the integer b and the integer x; and (c) returning instruction code directing the computer to evaluate the first and second comparisons cooperatively, at lower complexity than the combined complexities of the first and second comparisons enacted separately.
1 . A quantum computer comprising:
a qubit register including a plurality of qubits; and
an interface configured to physically manipulate the qubits of the qubit register according to a sequence of quantum-logic gates parsed from executable code,
wherein the executable code directs the quantum computer to execute an interval test to determine whether an interval defined by integers a and b encloses an integer x, the interval test including a first comparison between the integer a and the integer x and a second comparison between the integer b and the integer x, and
wherein the interval test comprises evaluating the first and second comparisons cooperatively, at a lower complexity than the complexity of the first comparison enacted separately combined with the complexity of the second comparison enacted separately.
2 . The quantum computer of claim 1 wherein the executable code directs the computer to execute a Deutsch algorithm.
3 . The quantum computer of claim 1 wherein the executable code comprises a sequence of reversible quantum-logic gates translated from a sequence of Boolean logic gates.
4 . A method for compiling executable code for execution on a quantum computer, the method comprising:
receiving source code instructing the quantum computer to execute an interval test to determine whether an interval defined by integers a and b encloses an integer x;
decomposing the interval test into a first comparison between the integer a and the integer x and a second comparison between the integer b and the integer x; and
returning instruction code directing the quantum computer to evaluate the first and second comparisons cooperatively, at a lower complexity than the complexity of the first comparison enacted separately combined with the complexity of the second comparison enacted separately,
wherein the instruction code comprises a sequence of quantum-logic gates which operate on a register of physical of qubits of the quantum computer, via a hardware interface.
5 . The method of claim 4 wherein the instruction code comprises a straight-line sequence of Boolean AND, XOR, and NOT gates.
6 . The method of claim 5 wherein the complexity is proportional to a number of AND gates in the sequence.
7 . The method of claim 4 wherein the complexity is proportional to a number of Toffoli gates in the sequence.
8 . The method of claim 4 wherein the instruction code directs the quantum computer to implement the interval test via a Deutsch algorithm.
9 . The method of claim 8 wherein the instruction code directs the quantum computer to implement the interval test via a single comparator gate.
10 . The method of claim 8 wherein the instruction code directs the quantum computer to initialize an ancilla register to either |a or |b conditional on an input |y , where |y is a single-qubit basis state.
11 . The method of claim 10 wherein the instruction code directs the quantum computer to compare the ancilla register to |x prior to uncomputing the ancilla register.
12 . The method of claim 4 further comprising translating the instruction code into the executable code, and wherein the executable code includes a sequence of reversible quantum gates.
13 . The method of claim 4 wherein the instruction code directs the quantum computer to evaluate each of the first and second comparisons as respective first and second AND/OR chains x 1 ∘ƒ(x 1 , . . . , x n ), where ƒ is a Boolean function of bit values x i of the integer x, and where ∘ is an AND operator or an OR operator.
14 . The method of claim 13 wherein ƒ=x 1 c 1 (x 2 c 2 ( . . . (x n−1 c n−1 x n ) . . . )), where, for any odd value (a 1 . . . a n1 ) of the integer a, c i =OR if a i =0 and c i =AND if a i =1.
15 . The method of claim 14 wherein the instruction code directs the quantum computer to evaluate the first and second AND/OR chains recursively, thereby shortening each of the AND/OR chains until a prepended operator of the first AND/OR chain differs from the prepended operator of the second AND/OR chain.
16 . The method of claim 15 wherein the instruction code directs the quantum computer to evaluate one or more if-then-else functions on the first and second AND/OR chains when the prepended operator of the first AND/OR chain differs from the prepended operator of the second AND/OR chain.
17 . The method of claim 16 wherein the instruction code directs the quantum computer to expand the one or more if-then-else functions in terms of additional AND/OR chains.
18 . The method of claim 4 further comprising incorporating the instruction code into a cryptographic program.
19 . A server computer system coupled operatively to a quantum computer, the server computer system comprising:
a network interface configured to receive source code instructing the quantum computer to execute an interval test to determine whether an interval defined by integers a and b encloses an integer x; and
a compiler configured to:
decompose the interval test into a first comparison between the integer a and the integer x and a second comparison between the integer b and the integer x, and
return instruction code directing the computer to evaluate the first and second comparisons cooperatively, at a lower complexity than the complexity of the first comparison enacted separately combined with the complexity of the second comparison enacted separately,
wherein the instruction code comprises a sequence of quantum-logic gates which operate on a register of physical of qubits of the quantum computer, via a hardware interface.