Measurement based uncomputation for quantum circuit optimization
Methods and apparatus for optimizing a quantum circuit. In one aspect, a method includes identifying one or more sequences of operations in the quantum circuit that un-compute respective qubits on which the quantum circuit operates; generating an adjusted quantum circuit, comprising, for each identified sequence of operations in the quantum circuit, replacing the sequence of operations with an X basis measurement and a classically-controlled phase correction operation, wherein a result of the X basis measurement acts as a control for the classically-controlled correction phase operation; and executing the adjusted quantum circuit.
1. A method for uncomputing a first table lookup operation, the method comprising:
identifying, from an address register of qubits, a set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation, wherein qubits in the address register represent respective bit values;
computing i) a first qubit in the address register and ii) a second qubit, wherein the first qubit represents a least significant bit of the respective bit values and the second qubit comprises an ancilla qubit prepared in a 1 state, the computing comprising
applying a first CNOT operation to the first qubit and the second qubit, wherein the first qubit acts as a control for the first CNOT operation, and
applying a first Hadamard gate to the first qubit and a second Hadamard gate to the second qubit;
performing a classically controlled phase correction operation based on the identified set of qubit states, comprising applying a second table lookup operation from a fixup table onto the first qubit and second qubit to negate amplitudes of the states in the identified set of qubit states; and
uncomputing the first qubit and the second qubit.
2. The method of claim, 1 , wherein uncomputing the first qubit and the second qubit comprises:
applying a third Hadamard gate to the first qubit and a fourth Hadamard gate to the second qubit; and
applying a second CNOT operation to the first qubit and the second qubit, wherein the first qubit acts as a control for the second CNOT operation.
3. The method of claim 1 , wherein entries of the fixup table specify respective two output bits defined by the identified set of states.
4. The method of claim 1 , wherein entries F j of the fixup table F are expressed as
F
j
=
{
00
(
2
j
∉
S
)
∧
(
2
j
+
1
∉
S
)
01
(
2
j
∈
S
)
∧
(
2
j
+
1
∉
S
)
10
(
2
j
∉
S
)
∧
(
2
j
+
1
∈
S
)
11
(
2
j
∈
S
)
∧
(
2
j
+
1
∈
S
)
where S represents the determined set of states.
5. The method of claim 1 , wherein identifying, from the address register of qubits, the set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation comprises using X basis measurements of qubits in a corresponding target register.
6. The method of claim 1 , wherein the set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation comprise a subset of address register states.
7. The method of claim 1 , wherein a state of the address register encodes address information that determines a respective state of a target register, a state of the target register encodes a target output, and a relationship between each state of the address register and each state of the target register is represented as a table.
8. The method of claim 7 , wherein each entry in the table is represented by a respective multi-control multi-target CNOT operation, wherein qubits in the address register act as controls and qubits in the target register are targets for the CNOT operation.
9. The method of claim 8 , wherein each qubit in the address register uses one control and each qubit in the target register uses one target for the CNOT operation.
10. The method of claim 1 , wherein identifying, from the address register of qubits, the set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation comprises measuring qubits in a target register in the X basis to determine a value of an observable, the observable comprising Pauli-X operators on qubits toggled by a corresponding compute table lookup operation.
11. An apparatus comprising:
one or more classical processors; and
quantum computing hardware in data communication with the one or more classical processors,
wherein the one or more classical processors comprise one or more storage devices storing instructions that are operable, when executed by the one or more classical processors, to cause the one or more classical processors to perform operations comprising:
identifying, from an address register of qubits, a set of qubit states that require an amplitude negation to complete an uncomputation of a first table lookup operation, wherein qubits in the address register represent respective bit values;
computing i) a first qubit in the address register and ii) a second qubit, wherein the first qubit represents a least significant bit of the respective bit values and the second qubit comprises an ancilla qubit prepared in a 1 state, the computing comprising
applying a first CNOT operation to the first qubit and the second qubit, wherein the first qubit acts as a control for the first CNOT operation, and
applying a first Hadamard gate to the first qubit and a second Hadamard gate to the second qubit;
performing a classically controlled phase correction operation based on the identified set of qubit states, comprising applying a second table lookup operation from a fixup table onto the first qubit and second qubit to negate amplitudes of the states in the identified set of qubit states; and
uncomputing the first qubit and the second qubit.
12. The apparatus of claim 11 , wherein the quantum computing hardware comprises:
one or more registers of qubits;
a plurality of control lines coupled to the one or more registers of qubits; and
a plurality of control circuits coupled to the plurality of control lines.
13. The apparatus of claim, 11 , wherein uncomputing the first qubit and the second qubit comprises:
applying a third Hadamard gate to the first qubit and a fourth Hadamard gate to the second qubit; and
applying a second CNOT operation to the first qubit and the second qubit, wherein the first qubit acts as a control for the second CNOT operation.
14. The apparatus of claim 11 , wherein entries of the fixup table specify respective two output bits defined by the identified set of states.
15. The apparatus of claim 11 , wherein entries F j of the fixup table F are expressed as
F
j
=
{
00
(
2
j
∉
S
)
∧
(
2
j
+
1
∉
S
)
01
(
2
j
∈
S
)
∧
(
2
j
+
1
∉
S
)
10
(
2
j
∉
S
)
∧
(
2
j
+
1
∈
S
)
11
(
2
j
∈
S
)
∧
(
2
j
+
1
∈
S
)
where S represents the determined set of states.
16. The apparatus of claim 11 , wherein identifying, from the address register of qubits, the set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation comprises using X basis measurements of qubits in a corresponding target register.
17. The apparatus of claim 11 , wherein the set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation comprise a subset of address register states.
18. The apparatus of claim 1 , wherein a state of the address register encodes address information that determines a respective state of a target register, a state of the target register encodes a target output, and a relationship between each state of the address register and each state of the target register is represented as a table.
19. The apparatus of claim 18 , wherein each entry in the table is represented by a respective multi-control multi-target CNOT operation, wherein qubits in the address register act as controls and qubits in the target register are targets for the CNOT operation.
20. The apparatus of claim 11 , wherein identifying, from the address register of qubits, the set of qubit states that require an amplitude negation to complete an uncomputation of the first table lookup operation comprises measuring qubits in a target register in the X basis to determine a value of an observable, the observable comprising Pauli-X operators on qubits toggled by a corresponding compute table lookup operation.