Quantum circuit embedding by simulated annealing
Mapping of logical qubits to physical qubits is provided. In various embodiments, a first candidate subgraph is selected from a hardware graph. The hardware graph represents a physical quantum circuit. The hardware graph comprises a plurality of nodes corresponding to physical qubits and a plurality of edges corresponding to coupling among the plurality of qubits. An accepted subgraph is determined by: setting the accepted subgraph to be the first candidate subgraph; mapping a quantum circuit comprising a plurality of logical qubits to the accepted subgraph; generating a second candidate subgraph of the hardware graph based on the accepted subgraph; mapping the quantum circuit to the second candidate subgraph; comparing fidelities of the accepted subgraph and the second candidate subgraph for the quantum circuit; if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph; if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.
1. A method of mapping a quantum circuit to hardware, the method comprising:
selecting a first candidate subgraph of a hardware graph, the hardware graph representing a physical quantum circuit, the hardware graph comprising a plurality of nodes corresponding to physical qubits and a plurality of edges corresponding to coupling of the plurality of physical qubits;
determining an accepted subgraph by:
setting the accepted subgraph to be the first candidate subgraph;
mapping a quantum circuit comprising a plurality of logical qubits to the accepted subgraph;
generating a second candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the second candidate subgraph;
comparing fidelities of the accepted subgraph and the second candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.
2. The method of claim 1 , wherein selecting the first candidate subgraph comprises selecting a random node of the hardware graph, and performing a depth-first search therefrom.
3. The method of claim 1 , wherein generating the second candidate subgraph from the accepted subgraph comprises selecting a random node of the first candidate subgraph, and performing a depth-first search on the hardware graph therefrom.
4. The method of claim 1 , wherein generating the second candidate subgraph from the accepted subgraph comprises reversing the placement of at least two of the logical qubits in the accepted subgraph.
5. The method of claim 1 , wherein generating the second candidate subgraph from the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.
6. The method of claim 1 , wherein the time-dependent probability is monotonically decreasing.
7. The method of claim 1 , wherein determining an accepted subgraph further comprises repeatedly:
generating an additional candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the additional candidate subgraph;
comparing fidelities of the accepted subgraph and the additional candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.
8. The method of claim 7 , wherein generating the additional candidate subgraph based on the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.
9. The method of claim 7 , wherein determining an accepted subgraph further comprises:
ceasing said repetition after a predetermined number of cycles.
10. A computer program product for mapping a quantum circuit to hardware, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform a method comprising:
selecting a first candidate subgraph of a hardware graph, the hardware graph representing a physical quantum circuit, the hardware graph comprising a plurality of nodes corresponding to physical qubits and a plurality of edges corresponding to coupling of the plurality of physical qubits;
determining an accepted subgraph by:
setting the accepted subgraph to be the first candidate subgraph;
mapping a quantum circuit comprising a plurality of logical qubits to the accepted subgraph;
generating a second candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the second candidate subgraph;
comparing fidelities of the accepted subgraph and the second candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.
11. The computer program product of claim 10 , wherein selecting the first candidate subgraph comprises selecting a random node of the hardware graph, and performing a depth-first search therefrom.
12. The computer program product of claim 10 , wherein generating the second candidate subgraph from the accepted subgraph comprises selecting a random node of the first candidate subgraph, and performing a depth-first search on the hardware graph therefrom.
13. The computer program product of claim 10 , wherein generating the second candidate subgraph from the accepted subgraph comprises reversing the placement of at least two of the logical qubits in the accepted subgraph.
14. The computer program product of claim 10 , wherein generating the second candidate subgraph from the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.
15. The computer program product of claim 10 , wherein the time-dependent probability is monotonically decreasing.
16. The computer program product of claim 10 , wherein determining an accepted subgraph further comprises repeatedly:
generating an additional candidate subgraph of the hardware graph based on the accepted subgraph;
mapping the quantum circuit to the additional candidate subgraph;
comparing fidelities of the accepted subgraph and the additional candidate subgraph for the quantum circuit;
if the fidelity of the second candidate subgraph is greater than the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph;
if the fidelity of the second candidate subgraph is less than or equal to the fidelity of the accepted subgraph, setting the accepted subgraph to be the second candidate subgraph with a time-dependent probability.
17. The computer program product of claim 16 , wherein generating the additional candidate subgraph based on the accepted subgraph comprises randomly performing one of: i) selecting a random node of the accepted subgraph, and performing a depth-first search on the hardware graph therefrom; or ii) reversing the placement of at least two nodes in the accepted subgraph.
18. The computer program product of claim 16 , wherein determining an accepted subgraph further comprises:
ceasing said repetition after a predetermined number of cycles.