Accelerated pattern matching method on a quantum computing system

Patent metadata

Field	Value
Publication number	US-11823010-B2
Application number	US-202117313671-A
Country	US
Kind code	B2
Filing date	May 6, 2021
Priority date	May 28, 2020
Publication date	Nov 21, 2023
Grant date	Nov 21, 2023

Abstract

A method of determining a pattern in a sequence of bits using a quantum computing system includes setting a first register of a quantum processor in a superposition of a plurality of string index states, encoding a bit string in a second register of the quantum processor, encoding a bit pattern in a third register of the quantum processor, circularly shifting qubits of the second register conditioned on the first register, amplifying an amplitude of a state combined with the first register in which the circularly shifted qubits of the second register matches qubits of the third register, measuring an amplitude of the first register and determining a string index state of the plurality of string index states associated with the amplified state, and outputting, by use of a classical computer, a string index associated with the first register in the measured state.

First claim

The invention claimed is:

1. A method of determining a pattern in a sequence of bits using a quantum computing system comprising a classical computer and a quantum processor, the method comprising:
setting a first register of the quantum processor in a superposition of a plurality of string index states, each of which is associated with a string index, wherein the quantum processor comprises a plurality of qubits;
encoding a bit string in a second register of the quantum processor;
encoding a bit pattern in a third register of the quantum processor;
circularly shifting qubits of the second register conditioned on the first register in each string index state in the superposition of the plurality of string index states;
amplifying an amplitude of a state combined with the first register in a string index state of the plurality of string index states in which the circularly shifted qubits of the second register matches qubits of the third register;
measuring an amplitude of the first register and determining the string index state of the plurality of string index states associated with the amplified state; and
outputting, by use of the classical computer, the string index associated with the first register in the measured state.

2. The method according to claim 1 , further comprising:
selecting, by use of the classical computer, the bit string and the bit pattern to be searched within the bit string, each bit of the bit string having a string index.

3. The method according to claim 1 , wherein each qubit of the plurality of qubits comprises a trapped ion having two frequency-separated states.

4. The method according to claim 3 , further comprising:
preparing the quantum processor in an initial state by setting, by a system controller, each trapped ion in the quantum processor in the lower energy state of the two frequency-separated states.

5. The method according to claim 4 , wherein setting the first register of the quantum processor in the superposition of the plurality of string index states comprises transferring, by the system controller, each trapped ion in the first register in a superposition of the two frequency-separated states.

6. The method according to claim 4 , wherein encoding the bit string in the second register of the quantum processor comprises applying, by the system controller, a combination of single-qubit gate operations to the second register of the quantum processor.

7. The method according to claim 4 , wherein encoding the bit pattern in the third register of the quantum processor comprises applying, by the system controller, a combination of single-qubit gate operations to the third register of the quantum processor.

8. The method according to claim 4 , wherein circularly shifting qubits of the second register conditioned on the first register comprises applying, by the system controller, a combination of single-qubit gate operations and two-qubit gate operations to the first and second registers of the quantum processor.

9. The method according to claim 8 , wherein the two-qubit gate operations comprise controlled-SWAP operations applied to the second register conditioned on the first register.

10. The method according to claim 8 , wherein the two-qubit gate operations comprise controlled-SWAP operations applied to the second register conditioned on a plurality of ancillary qubits in which the first register is copied by fan-out CNOT operations applied on the plurality of ancillary qubits conditioned on the first register.

11. The method according to claim 4 , wherein amplifying the state combined with the first register in the string index state of the plurality of string index states in which the circularly shifted qubits of the second register matches qubits of the third register comprises applying, by the system controller, a combination of single-qubit gate operations and two-qubit gate operations to the second and third registers of the quantum processor.

12. A quantum computing system, comprising:
a quantum processor comprising a group of trapped ions, each of the trapped ions having two frequency-separated states;
one or more lasers configured to emit a laser beam, which is provided to trapped ions in the quantum processor;
a classical computer configured to:
select a bit string and a bit pattern to be searched within the bit string, each bit of the bit string having a string index; and

a system controller configured to:
set a first register of the quantum processor in a superposition of a plurality of string index states, each of which is associated with a string index, wherein the quantum processor comprises a plurality of qubits;
encode the bit string in a second register of the quantum processor;
encode the bit pattern in a third register of the quantum processor;
circularly shift qubits of the second register conditioned on the first register in each string index state in the superposition of the plurality of string index states;
amplify an amplitude of a state combined with the first register in a string index state of the plurality of string index states in which the circularly shifted qubits of the second register matches qubits of the third register; and
measure an amplitude of the first register and determining the string index state of the plurality of string index states associated with the amplified state,

wherein the classical computer is further configured to:
output the string index associated with the first register in the measured state.

13. The quantum computing system according to claim 12 , wherein the system controller is further configured to:
prepare the quantum processor in an initial state by setting each trapped ion in the quantum processor in the lower energy state of the two frequency-separated states.

14. The quantum computing system according to claim 12 , wherein setting the first register of the quantum processor in the superposition of the plurality of string index states comprises transferring each trapped ion in the first register in a superposition of the two frequency-separated states.

15. The quantum computing system according to claim 12 , wherein encoding the bit string in the second register of the quantum processor comprises applying a combination of single-qubit gate operations to the second register of the quantum processor.

16. The quantum computing system according to claim 12 , wherein encoding the bit pattern in the third register of the quantum processor comprises applying a combination of single-qubit gate operations to the third register of the quantum processor.

17. The quantum computing system according to claim 12 , wherein circularly shifting qubits of the second register conditioned on the first register comprises applying, by the system controller, a combination of single-qubit gate operations and two-qubit gate operations to the first and second registers of the quantum processor.

18. The quantum computing system according to claim 17 , wherein the two-qubit gate operations comprise controlled-SWAP operations applied to the second register conditioned on the first register.

19. The quantum computing system according to claim 17 , wherein the two-qubit gate operations comprise controlled-SWAP operations applied to the second register conditioned on a plurality of ancillary qubits in which the first register is copied by fan-out CNOT operations applied on the plurality of ancillary qubits conditioned on the first register.

20. The quantum computing system according to claim 12 , wherein amplifying the

Assignees

• Ionq Inc
• Univ Maryland

Inventors

• Niroula Pradeep
• Nam Yunseong

Classifications

• G06N10/20

  Models of quantum computing, e.g. quantum circuits or universal quantum computers · CPC title

• G06N10/80 Primary

  Quantum programming, e.g. interfaces, languages or software-development kits for creating or handling programs capable of running on quantum computers; Platforms for simulating or accessing quantum computers, e.g. cloud-based quantum computing · CPC title

• G06N10/00 Primary

  Quantum computing, i.e. information processing based on quantum-mechanical phenomena · CPC title

• G06F9/30032

  Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE · CPC title

• G06F9/30101

  Special purpose registers · CPC title