Source-linked AI summary
Efficient Toffoli Gates Using Qudits
T. C. Ralph, K. J. Resch, A. Gilchrist
TL;DR
The paper addresses the resource cost of implementing Toffoli gates with qubit-only circuits. It introduces an accessible third state on one system and shows that this reduces controlled-sign gates from six to three, with optical implementations including deterministic, heralded, and post-selected schemes.
Problem
Implementing a three-qubit Toffoli gate requires five two-qubit gates generally and six controlled-sign or controlled-NOT gates, motivating more efficient constructions.
Method
The paper makes one target qubit a qutrit or higher-dimensional qudit during computation, then examines abstract and optical implementations using controlled-sign interactions.
Results
Three controlled-sign gates implement a Toffoli gate with a qutrit, while an n-Toffoli requires 2n −1 two-qubit gates with an n+1-level qudit.
Takeaways & Limitations
Accessible extra levels can reduce Toffoli resource requirements and support optical implementations, including a heralded success probability of 1/32 and a post-selected probability of 1/72.
Abstract
from arXiv · showhide
The simplest decomposition of a Toffoli gate acting on three qubits requires {\em five} 2-qubit gates. If we restrict ourselves to controlled-sign (or controlled-NOT) gates this number climbs to six. We show that the number of controlled-sign gates required to implement a Toffoli gate can be reduced to just {\em three} if one of the three quantum systems has a third state that is accessible during the computation, i.e. is actually a qutrit. Such a requirement is not unreasonable or even atypical since we often artificially enforce a qubit structure on multilevel quantums systems (eg. atoms, photonic polarization and spatial modes). We explore the implementation of these techniques in optical quantum processing and show that linear optical circuits could operate with much higher probabilities of success.
I. INTRODUCTION
The paper motivates more efficient Toffoli-gate implementations against experimental hurdles in quantum computing. It proposes using an accessible third level on one system to reduce gate resources.
- Quantum computing promises major increases in computing power but faces many experimental implementation hurdles.
- The Toffoli gate acts on three qubits and, together with the Hadamard gate, forms perhaps the simplest universal gate set.
- Making one qubit a qutrit or qudit reduces the number of two-qubit gates required for a Toffoli gate.The additional level is used during the gate, while only qubit levels remain occupied afterward.
II. TOFFOLI GATE WITH QUDITS
A Toffoli-Sign gate can be implemented with three controlled-sign gates by temporarily using one target qubit as a qutrit. The construction generalizes to higher-order Toffoli gates with an n+1-level qudit.
- 3 controlled-sign gates implement a Toffoli gate when one qubit is allowed to be a qutrit, compared with 6 controlled-sign gates in a qubit-only circuit.The construction also uses single-qubit unitaries and assumes controlled-sign and Hadamard gates are available.
- The T-S gate applies a sign change to exactly one three-qubit basis component and implements the identity otherwise.Hadamards before and after the gate convert the T-S gate into a Toffoli gate.
- The XA gate exchanges qutrit states 0 and 2, while controlled-sign and CNOT gates act normally on qubit levels and as the identity when the target is in state 2.This temporary qutrit state enables the three-gate construction.
- The resulting T-S gate places the sign change on the |1, 0, 1⟩ component.
- 2n −1 two-qubit gates implement an n-Toffoli when an n+1-level qudit is available; a 5-Toffoli therefore requires 9 gates instead of 64.
III. OPTICAL IMPLEMENTATIONS
The paper maps the qudit construction onto optical encodings, using additional spatial modes and optical elements to realize the required operations. It considers deterministic, heralded, and post-selected optical implementations.
- A qutrit is created in dual-rail optics by adding a third spatial mode, with logical states encoded as |100⟩, |010⟩, and |001⟩.The optical modes may represent different polarization or spatial modes.
- The optical implementation uses linear optical elements together with proposed two-qubit optical gates to realize the qudit circuit.
- The paper considers deterministic gates based on strong nonlinearities, heralded non-deterministic gates, and post-selected measurement-induced nonlinearities.
A. Deterministic Gates
The optical implementation uses cross-Kerr interactions to realize controlled-sign gates, then combines them with an added spatial mode to implement the qutrit-assisted Toffoli-S gate. The required Kerr strength is not currently available, motivating nondeterministic alternatives.
- Cross-Kerr C-S gate: A strong cross-Kerr non-linearity implements an optical controlled-sign gate by inducing a phase shift only when both modes are occupied.Choosing χ = π flips the sign of one component while leaving the others unchanged.
- Qutrit-assisted implementation: Three χ3 interactions replace the five or six interactions required by usual qubit-only Toffoli implementations.The qutrit-assisted optical construction preserves the resource saving of the abstract circuit.
- Qutrit-assisted implementation: Polarizing beamsplitters and polarization rotation introduce a third spatial mode, providing the additional level needed for the control-gate sequence.The optical realization is shown as the T-S gate construction in Fig. 4.
- Practical limitation: The required strong Kerr materials are not presently available, so the paper turns to measurement-induced nondeterministic implementations.This is the main practical boundary of the deterministic optical approach.
B. Heralded Gates
The heralded optical construction replaces deterministic interactions with nondeterministic controlled-sign gates and a passive filter. It produces a T-S gate conditionally, with success heralded by measurement outcomes and an overall success probability of 1/32.
- Heralded circuit: Each heralded controlled-sign gate succeeds with probability 1/4 and requires an entangled photon pair.The circuit replaces the final two-qubit gate with a passive filter that succeeds with probability 1/2.
- Heralded circuit: The passive filter recombines the target modes and conditions on zero detection at one output port, with probability 1/2.This filtering step produces the conditional output state used for the T-S gate.
- Heralded circuit: The circuit conditions on correct photon-counting outcomes from the first two controlled-sign gates, giving an intermediate success probability of 1/16.The target modes are then processed with half-wave plates rather than a third controlled-sign gate.
- Outcome and scope: 1/32 is the overall success probability of the heralded T-S gate, with the phase flip occurring on the |H, H, V⟩ component.The probability combines the preceding 1/16 heralding condition with the filter's 1/2 success probability.
- Outcome and scope: The proposed heralded circuit requires five photons, making the experiment feasible in principle but difficult.The paper therefore considers a subsequent three-photon post-selected construction.
C. Postselected Gates
The paper proposes a post-selected optical T-S gate using an added target mode and interferometers, with success heralded by photon coincidence detection. The circuit applies a phase flip selectively through conditional interference while explicitly representing all optical modes.
- C. Postselected Gates: Post-selected gates use the photons as their own ancilla, with success heralded by detecting one photon for each qubit.This construction uses only the three photons representing the three qubits.
- C. Postselected Gates: The first interferometer conditionally routes the target photon and can induce a phase flip through interference controlled by the first control qubit.When the relevant control mode is unoccupied, the interferometer is anti-balanced and the photon couples with a phase flip; two-photon interference changes this behavior when it is occupied.
- C. Postselected Gates: The optical realization adds a target mode, producing seven modes in the central circuit while representing each input qubit with two modes.The figure assumes spatial modes for clarity, although polarization modes would be used where possible experimentally.
- C. Postselected Gates: The second interferometer applies the corresponding control-dependent routing so that output in the target mode occurs without an unwanted phase flip.The described paths ensure that target photons reaching the output target mode have the intended phase behavior.
IV. CONCLUSION
The paper concludes that allowing one qubit to access an additional level reduces Toffoli-gate resources and supports optical implementations. It reports improved success probabilities for heralded and post-selected optical gates, making near-term demonstrations more feasible.
- IV. CONCLUSION: A qutrit reduces a qubit-only Toffoli implementation from six controlled-sign gates to three.For an n-Toffoli, the required gate number is 2n −1 when an n+1-level qudit is available.
- IV. CONCLUSION: Deterministic optical quantum processing admits a natural implementation of the qutrit-based construction.
- IV. CONCLUSION: Heralded and post-selected optical Toffoli gates have reported success probabilities of 1/32 and 1/72, respectively.These results are presented as enabling experimental optical demonstrations and making small-scale applications more feasible.
- IV. CONCLUSION: Adding one quantum level makes Toffoli plus Hadamard universal, whereas controlled-sign plus Hadamard is non-universal without an additional π/8 gate.