A quantum algorithm provides for the encoding of an exponentially large number of classical data bits by use of a smaller (polynomially large) number of quantum bits (qubits). The development of this algorithm was prompted by the need, heretofore not satisfied, for a means of entering real-world binary data into a quantum computer. The data format provided by this algorithm is suitable for subsequent ultrafast quantum processing of the entered data. Potential applications lie in disciplines (e.g., genomics) in which one needs to search for matches between parts of very long sequences of data. For example, the algorithm could be used to encode the N-bit-long human genome in only log2N qubits. The resulting log2N-qubit state could then be used for subsequent quantum data processing — for example, to perform rapid comparisons of sequences.
Below are the steps of the algorithm, illustrated with the example of the fourbit string 0111:
- Specify a correspondence between (a) each classical bit in a string of 2n such bits and (b) a unique n-bit eigenstate in a set of 2n such eigenstates. For example, if a classical 2n-bit string is 0111, then the corresponding four 2-bit eigenstates could be |00>, |01>, |10>, and |11>.
- Construct a superposition, |ψ>, of equally weighted quantum states that is peaked at only those eigenstates that correspond to 1s in the classical bit string. In the example of the bit string 0111, the corresponding 2-qubit state would be |ψ>= 3-1/2 (|01> + |10> + |11>). In the general case, the superposition would be an entangled state of n qubits that encodes a specific sequence of 2n classical bits.
Compute the unitary transformation needed to obtain the superposition starting from an easy-to-make state (for example, |00>). Equivalently, compute a unitary matrix that maps the chosen state (e.g., |00>) into the state |ψ>. For the classical bit string 0111, the unitary matrix would be
To compute the matrix, first compute |ψ><ψ| (which gives one column of the matrix), then generate the remaining orthonormal vectors for the other columns.
- By use of software developed previously for this purpose, compute the form of a feasible quantum circuit equivalent to the unitary matrix. The quantum circuit could be implemented in one of several physical embodiments: for example, spin-based, charge-based, optical, or superconducting quantum computer hardware.
This work was done by Colin Williams of Caltech for NASA’s Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Information Sciences category.
In accordance with Public Law 96-517, the contractor has elected to retain title to this invention. Inquiries concerning rights for its commercial use should be addressed to:
Innovative Technology Assets Management
Mail Stop 202-233
4800 Oak Grove Drive
Pasadena, CA 91109-8099
Refer to NPO-30209, volume and number of this NASA Tech Briefs issue, and the page number.