Quantum circuit synthesis using deterministic walks
There is provided a method for implementing an algorithm for forming, or synthesizing, quantum circuits on a system capable of performing the quantum circuit synthesis by using a deterministic walk (i.e. a pseudo-random walk with a random or pseudo-random starting point). In one implementation, the deterministic walk is performed using a parallel search algorithm. In an implementation of the parallel search algorithm, a user utilizes a programming language to write instructions for a compiler. Then, a meet in the middle approach is utilized to separate the circuit into two halves. Next, the parallel search technique is used to find a claw, or a pair, which satisfies the circuit analysis. Subsequently there is the production of a result and/or a synthesis of the circuit if the pair is found.
1. A method for synthesizing quantum circuits, the method comprising:
performing one or more deterministic walks on a search space by, for each of multiple processors in parallel:
i. generating a starting point;
ii. mapping the starting point to a candidate matrix or a sequence of quantum gates;
iii. applying a deterministic function to the candidate matrix to generate a new point, referred to as a current point;
iv. if the current point is distinguished:
compare the current point to a database of existing distinguished points shared amongst the processors;
if the same distinguished point is not present in the database, it is added, then the processor returns to i;
if the same distinguished point is present in the database, the two corresponding walks are checked for a claw;
if a claw is found, the processor returns a solution;
if no claw is found, the processor discards or overwrites the existing distinguished point and returns to i;
v. if the current point is not distinguished, mapping the current point to a new candidate matrix and returning to iii;
performing a circuit synthesis according to results of the one or more deterministic walks; and
outputting a synthesized quantum circuit.
2. The method of claim 1 , wherein the starting point for the one or more deterministic walks is chosen randomly.
3. The method of claim 1 , further comprising determining a plurality of search spaces.
4. The method of claim 3 , wherein there are two search spaces.
5. The method of claim 4 , wherein the two spaces are of equal size.
6. The method of claim 1 , wherein a meet in the middle algorithm is used.
7. The method of claim 1 , wherein the parallel search comprises a mapping from unitary matrices to binary strings.
8. The method of claim 1 , wherein the parallel search comprises a step of generating a list of distinguished points.
9. The method of claim 1 , wherein the circuit synthesis comprises a step of finding a list of unitary matrices having a product within an error tolerance of a given value.
10. The method of claim 9 , wherein the error tolerance is less than a machine precision value.
11. The method of claim 10 , wherein the error tolerance is 0.
12. The method of claim 1 , wherein the circuit synthesis uses a gate set.
13. The method of claim 12 , wherein the gate set is universal.
14. The method of claim 1 , wherein the deterministic walk comprises:
applying a hash function to the candidate matrix to generate the new point;
creating a distinguished point structure;
storing the distinguished point structure in the database; and
finding a merging of trails with matrices of two different types.
15. The method of claim 14 , wherein a plurality of collectors, workers, and verifiers are used to perform the method.
16. The method of claim 15 , wherein inter-processor communication is used.
17. A non-transitory computer readable medium comprising computer executable instructions for synthesizing quantum circuits, comprising instructions for:
performing one or more deterministic walks on a search space by, for each of multiple processors in parallel:
i. generating a starting point;
ii. mapping the starting point to a candidate matrix or a sequence of quantum gates;
iii. applying a deterministic function to the candidate matrix to generate a new point, referred to as a current point;
iv. if the current point is distinguished:
compare the current point to a database of existing distinguished points shared amongst the processors;
if the same distinguished point is not present in the database, it is added, then the processor returns to i;
if the same distinguished point is present in the database, the two corresponding walks are checked for a claw;
if a claw is found, the processor returns a solution;
if no claw is found, the processor discards or overwrites the existing distinguished point and returns to i;
v. if the current point is not distinguished, mapping the current point to a new candidate matrix and returning to iii;
performing a circuit synthesis according to results of the one or more deterministic walks; and
outputting a synthesized quantum circuit.
18. A quantum computing system comprising a processor and memory, the memory comprising computer executable instructions for synthesizing quantum circuits by:
performing one or more deterministic walks on a search space by, for each of multiple processors in parallel:
i. generating a starting point;
ii. mapping the starting point to a candidate matrix or a sequence of quantum gates;
iii. applying a deterministic function to the candidate matrix to generate a new point, referred to as a current point;
iv. if the current point is distinguished:
compare the current point to a database of existing distinguished points shared amongst the processors;
if the same distinguished point is not present in the database, it is added, then the processor returns to i;
if the same distinguished point is present in the database, the two corresponding walks are checked for a claw;
if a claw is found, the processor returns a solution;
if no claw is found, the processor discards or overwrites the existing distinguished point and returns to i;
v. if the current point is not distinguished, mapping the current point to a new candidate matrix and returning to iii;
performing a circuit synthesis according to results of the one or more deterministic walks; and
outputting a synthesized quantum circuit.
19. The system of claim 18 , wherein the deterministic walk comprises:
applying a hash function to the candidate matrix to generate the new point;
creating a distinguished point structure;
storing the distinguished point structure in the database; and
finding a merging of trails with matrices of two different types.