This project begins by exploring classical logic gate structures, focusing on two-input one-output (2→1) and two-input two-output (2→2) gates to identify all functionally distinct pairs of classical operations. This will helpus lay the foundation for understanding complexity and universality in small gate systems. We then extend this framework into the quantum realm, classifying all two-qubit quantum gates using the Cartan (KAK) decomposition. Each quantum gate is mapped to a canonical triple within the Weyl chamber, a reduced geometric region that captures non-local behavior up to local unitary equivalence. The chamber is discretized at fixed resolution, and representative gates are generated for each point. Using Makhlin invariants, we determine which gates are locally equivalent to universal entangling gates such as CNOT and the one with the highest efficiency.
Introduction
Introduction
Classical 2-to-1 Gates
Classical 2-to-1 Gates
Classical 2→1 gates take two input bits and produce a single output bit, representing Boolean functions over four possible input combinations. There are 42 = 16 such gates, including familiar operations like AND, OR, XOR, and NAND. Among these, gates like NAND are universal, meaning they can be composed to construct any Boolean function. This classical notion of universality serves as a foundation for understanding universality in quantum computation, where certain two-qubit gates, when paired with local operations, can generate any unitary transformation.
Classical 2→1 gates take two input bits and produce a single output bit, representing Boolean functions over four possible input combinations. There are = 16 such gates, including familiar operations like AND, OR, XOR, and NAND. Among these, gates like NAND are universal, meaning they can be composed to construct any Boolean function. This classical notion of universality serves as a foundation for understanding universality in quantum computation, where certain two-qubit gates, when paired with local operations, can generate any unitary transformation.
4
2
This code highlights the universality of NAND gates by constructing and visualizing all other 16 2x1 gates solely from NAND operations.
In[]:=
parseNandArgs[expr_String]:=Module[{inside,chars,levels,commaPositions,commaPos},inside=StringTake[expr,{6,-2}];chars=Characters[inside];levels=Rest@FoldList[(#1+Which[#2=="(",1,#2==")",-1,True,0])&,0,chars];commaPositions=Flatten@Position[Thread[{chars,levels}],{",",0}];If[Length[commaPositions]==0,Return[{}]];commaPos=First[commaPositions];{StringTrim[StringJoin[Take[chars,commaPos-1]]],StringTrim[StringJoin[Drop[chars,commaPos]]]}]
Extracts the two arguments from a NAND(...) string while correctly handling nested parentheses.
In[]:=
inputPairs=Tuples[{0,1},2];allFuncs=Tuples[{0,1},4];NAND[a_,b_]:=1-a*b
Generates all possible 2-bit input pairs, defines all 2-input Boolean functions, and defines the NAND operation.
In[]:=
evalFunc[func_,a_,b_]:=Module[{idx},idx=Position[inputPairs,{a,b}][[1,1]];func[[idx]]]applyNandOnFuncs[f1_,f2_]:=Table[NAND[evalFunc[f1,a,b],evalFunc[f2,a,b]],{a,0,1},{b,0,1}]//FlattentoFuncForm[list_]:=Partition[list,4][[1]]
Evaluates Boolean functions on input pairs, applies the NAND gate to two functions over all inputs, and formats the result as a 4-entry truth table.
In[]:=
expr0="NAND(NAND(NAND(a,a),a),NAND(NAND(a,a),a))";expr1="NAND(NAND(a,a),a)";exprA="a";exprB="b";baseExprs=Association[{0,0,0,0}->expr0,{1,1,1,1}->expr1,{0,1,0,1}->exprA,{0,0,1,1}->exprB];generated=Keys[baseExprs];expressions=baseExprs;queue=generated;
Defines NAND-based expressions for constant and input functions, initializes the expression map, and sets up the queue for generating all Boolean functions.
In[]:=
generateAllNandHelper[f1_,generated_,expressions_,queue_,allFuncs_]:=Module[{newFuncs={},newExprs=expressions,newFunc,newFuncRev},Map[(newFunc=toFuncForm[applyNandOnFuncs[f1,#]];If[!MemberQ[generated,newFunc],AppendTo[newFuncs,newFunc];newExprs[newFunc]="NAND("<>newExprs[f1]<>", "<>newExprs[#]<>")";];newFuncRev=toFuncForm[applyNandOnFuncs[#,f1]];If[!MemberQ[generated,newFuncRev],AppendTo[newFuncs,newFuncRev];newExprs[newFuncRev]="NAND("<>newExprs[#]<>", "<>newExprs[f1]<>")";];)&,generated];newFuncs=DeleteDuplicates[newFuncs];generateAllNand[Join[generated,newFuncs],newExprs,Join[Rest[queue],newFuncs],allFuncs]];generateAllNand[generated_,expressions_,queue_,allFuncs_]:=Module[{f1},If[Length[generated]>=Length[allFuncs]||Length[queue]==0,{generated,expressions},f1=First[queue];generateAllNandHelper[f1,generated,expressions,queue,allFuncs]]];
Builds all 2-input Boolean functions by iteratively combining previously generated ones using the NAND operation in all input orders.
ClearAll[circuitId,circuitWires,circuitNodes];resetCircuitState[]:=(circuitId=0;circuitWires={};circuitNodes={};);buildCircuit[expr_String]:=Which[StringMatchQ[expr,"a"|"b"],circuitId++;AppendTo[circuitNodes,ToString[circuitId]->expr];ToString[circuitId],StringStartsQ[expr,"NAND("],Module[{args,left,right,thisID},args=parseNandArgs[expr];If[Length[args]!=2,circuitId++;AppendTo[circuitNodes,ToString[circuitId]->"?"];Return[ToString[circuitId]]];left=buildCircuit[args[[1]]];right=buildCircuit[args[[2]]];circuitId++;thisID=ToString[circuitId];AppendTo[circuitNodes,thisID->"NAND"];circuitWires=Join[circuitWires,{left->thisID,right->thisID}];thisID],True,circuitId++;AppendTo[circuitNodes,ToString[circuitId]->"?"];ToString[circuitId]];drawCircuit[exprStr_String]:=Module[{},resetCircuitState[];buildCircuit[exprStr];Graph[circuitWires,VertexLabels->Table[circuitNodes[[i,1]]->Placed[If[circuitNodes[[i,2]]==="NAND",Style[circuitNodes[[i,2]],FontSize->12],Style[circuitNodes[[i,2]],FontSize->16,Bold]],Above],{i,Length[circuitNodes]}],VertexStyle->LightBlue,VertexSize->Medium,GraphLayout->"LayeredDigraphEmbedding"]];
Generates a circuit diagram as a graph from a NAND expression string
In[]:=
tableData=Table[{func,expressions[func],drawCircuit[expressions[func]]},{func,Keys[expressions]}];Grid[Prepend[tableData,{Style["Truth Table",Bold],Style["NAND Expression",Bold],Style["Circuit Diagram",Bold]}],Frame->All,Alignment->Center,Spacings->{2,2}]
Out[]=
Truth Table | NAND Expression | Circuit Diagram |
{0,0,0,0} | NAND(NAND(NAND(a,a),a),NAND(NAND(a,a),a)) | |
{1,1,1,1} | NAND(NAND(a,a),a) | |
{0,1,0,1} | a | |
{0,0,1,1} | b | |
{1,0,1,0} | NAND(NAND(NAND(a,a),a), a) | |
{1,1,0,0} | NAND(NAND(NAND(a,a),a), b) | |
{1,1,1,0} | NAND(a, b) | |
{1,0,1,1} | NAND(a, NAND(NAND(NAND(a,a),a), b)) | |
{1,1,0,1} | NAND(b, NAND(NAND(NAND(a,a),a), a)) | |
{0,1,1,1} | NAND(NAND(NAND(NAND(a,a),a), a), NAND(NAND(NAND(a,a),a), b)) | |
{0,0,0,1} | NAND(NAND(a, b), NAND(NAND(a,a),a)) | |
{1,0,0,1} | NAND(NAND(a, b), NAND(NAND(NAND(NAND(a,a),a), a), NAND(NAND(NAND(a,a),a), b))) | |
{0,1,0,0} | NAND(NAND(a, NAND(NAND(NAND(a,a),a), b)), NAND(NAND(a,a),a)) | |
{0,1,1,0} | NAND(NAND(a, NAND(NAND(NAND(a,a),a), b)), NAND(b, NAND(NAND(NAND(a,a),a), a))) | |
{0,0,1,0} | NAND(NAND(b, NAND(NAND(NAND(a,a),a), a)), NAND(NAND(a,a),a)) | |
{1,0,0,0} | NAND(NAND(NAND(NAND(NAND(a,a),a), a), NAND(NAND(NAND(a,a),a), b)), NAND(NAND(a,a),a)) |
Note: These may not be the most minimal routes. This shows completeness only.
Classical 2 to 2 gates
Classical 2 to 2 gates
2-to-2 gates extend the concept of 2-input, 1-output Boolean functions by producing two output bits from two input bits, enabling more flexible and nuanced operations. This extension allows us to explore a broader class of logical transformations, including reversible gates that preserve information.
While 2-to-1 functions span all 16 Boolean outputs, they are inherently irreversible, once a single bit is output, some information is lost and cannot be recovered. In contrast, only a subset of the 256 possible 2-to-2 functions are reversible, specifically, the bijective ones that map each input pair to a unique output pair. By focusing on this smaller, structured subspace of reversible 2-to-2 gates, we can investigate how universality and efficient composition play out in settings where information preservation is required, which is essential for our work with quantum circuits.
While 2-to-1 functions span all 16 Boolean outputs, they are inherently irreversible, once a single bit is output, some information is lost and cannot be recovered. In contrast, only a subset of the 256 possible 2-to-2 functions are reversible, specifically, the bijective ones that map each input pair to a unique output pair. By focusing on this smaller, structured subspace of reversible 2-to-2 gates, we can investigate how universality and efficient composition play out in settings where information preservation is required, which is essential for our work with quantum circuits.
Generates all possible 2-to-2 gate output mappings, check which are reversible by ensuring outputs are unique , and displays all reversible gates with their indices
Finding the Shortest Composition of Gates using Breadth First Search
Finding the Shortest Composition of Gates using Breadth First Search
In this section, we focus on understanding how to build complex reversible gates from simpler building blocks. The inputs are the basic two-bit combinations, and the target gate refers to a specific reversible 2-to-2 gate we aim to construct. The generators are a selected set of reversible gates used as fundamental components to compose more complex gates. Using these generators, the goal is to find the shortest sequence of compositions that equals the target gate.
Lists all possible 2-bit inputs, creates all 24 reversible gates that map those inputs (same as above)
Defines how to compose two 2-to-2 gates, meaning it applies gate g1 to the inputs first, then passes the result through gate g2, computing the overall transformation g2(g1(x)). It does this by finding where each output of g1 appears in the input list and then selecting the corresponding output from g2.
Performs a breadth-first search to find the shortest sequence of generator gates that compose to a given target gate. Starting from the identity gate, it explores all possible compositions with the generator gates, tracking visited gates to avoid repetition. When the target gate is reached, it returns the sequence of generators used to obtain it.
Using the generator set genSet = {{“00”, “01”, “11”, “10”}, {“00”, “10”, “01”, “11”}}, the function composes these gates step-by-step starting from the identity gate to rearrange the inputs. Applying these generators in sequence produces the target gate {“00”, “11”, “10”, “01”} with the minimal number of successive permutations of the input pairs.
Efficiency Analysis of Gate Pairs via Group Theory and Closure
Efficiency Analysis of Gate Pairs via Group Theory and Closure
Cycle Structure
Cycle Structure
Conjugacy and Cycle Type
Conjugacy and Cycle Type
Order of a Gate
Order of a Gate
Application
Application
Given a pair of generators (g1,g2) , we study the subgroup they generate:
This block of code evaluates all unordered pairs of reversible gates to analyze their generative power: for each pair, it computes the closure (all gates they can generate), the order and cycle type of their composition, and whether they are universal (able to generate all 24 reversible gates), assigning each pair a summary score based on both the product’s order and the size of the generated closure. The gates with the summary score of 0.52 have the best efficiency.
Calculates the order of a gate g, which is the minimum number of times g must be composed with itself to return to the identity gate, or returns ∞ if it does not do so within 100 steps.
Computes the closure of a set of generator gates by iteratively composing all pairs of known gates up to a specified depth, returning the set of all unique gates that can be built from the generators within that depth.
Introduction to the Quantum Framework
Introduction to the Quantum Framework
Each gate is converted to a permutation matrix that maps basis vectors accordingly
Verifies if each permutation matrix is unitary, confirming that it preserves inner products and is valid in quantum computing.
Why unitarity alone is not enough in quantum gate design
Why unitarity alone is not enough in quantum gate design
Discretizing Two-Qubit Gates Using Canonical Coordinates and the Weyl Chamber
Discretizing Two-Qubit Gates Using Canonical Coordinates and the Weyl Chamber
In the study of two-qubit quantum gates, one of the main challenges is the infinite dimensionality of the unitary group SU(4), which contains all possible two-qubit operations. Directly analyzing this continuous, uncountably infinite set to find universal gates or to classify gate behaviors is computationally infeasible. Therefore, a key step is to reduce this infinite space to a finite, manageable set of representatives that preserves the essential structure of two-qubit operations, especially their entangling properties. For now, we define universality as the ability of a set of gates to generate all other gates in this finite representative set, rather than the entire infinite group. This finite approximation is still highly valuable because any physically implementable quantum circuit can only approximate continuous operations to finite precision. By focusing on the ability to generate all gates within this discrete representative set, we ensure coverage of all essential classes of two-qubit operations up to a chosen precision.
Define Example Local Single Qubit Matrices: Pauli x,y,z
Perform the Canonical KAK Transformation Setup
Calculates three sorted canonical angles of unitary matrix U using a basis change by K and eigenphase extraction
Defines Discretization Parameters
Generates a flattened list of all triples
Plots the points in 3d
Distance Matching to Nearest Discrete Triple
As a concrete example of this decomposition’s utility, we apply it to two well-known two-qubit gates: CNOT and SWAP. By computing their canonical coordinates (c1,c2,c3 ), we can represent each gate as a point within the Weyl chamber and study how close they are to a discretized set of representative gates.
Filters for entangling gates
Parameterized Plotting of Quantum State Projections
Parameterized Plotting of Quantum State Projections
While standard 2D plots can illustrate data points or function curves, they often fall short when visualizing quantum state evolution, especially in the context of multi-component complex vectors. This visualization method, powered by the myPlot function, is purpose-built to display individual quantum state components in the complex plane, emphasizing their real and imaginary structure, relative phases, and label identity. Unlike traditional subplots that show aggregated behavior, this approach distinctly tracks how each basis state transforms under different quantum gates, offering a granular and annotated snapshot of gate action on amplitude-level detail. The use of color, marker, and labeling not only enhances interpretability but also supports pattern recognition across gate families, which is vital when comparing permutations, Pauli gates, and entangling transformations. Thus, this method supplements conventional plots with a component-wise, vector-level lens, making it a analytical tool for precise and visual quantum behavior tracing.
Visualizes each quantum state component in the complex plane with labels and styles, revealing structure standard plots miss.
Defines gates
Generates a discrete sample of two-qubit gates from the Weyl chamber by constructing matrix exponentials of weighted Pauli tensor products,
Generates labelled visualizations of how each gate transforms multiple test vectors, then organizes selected plots into a grid for comparative analysis
Classifying Two-Qubit Gates Using Makhlin Invariant
Classifying Two-Qubit Gates Using Makhlin Invariant
Define the KAK magic basis transformation matrix and its adjoint
Compute Makhlin invariants of a 2-qubit gate to classify entanglement
distance from CNOT in invariant space where small means similar behavior
The results show that there are 7 gates in our set that are universal. Since our earlier focus was on identifying whether a gate is universal by comparing its Makhlin invariants to those of CNOT, we can now refine our perspective to consider efficiency, how close a universal gate is to a “minimal” entangling gate in the Cartan space. Researchers group gates by conjugacy classes, treating any pair of gates equivalent under local operations as functionally identical. However, for practical quantum circuit design, conjugacy class membership is not enough, we need to evaluate how close a gate lies to CNOT in Cartan coordinates, because this affects how easily and efficiently we can approximate it using native gates. To measure this, we use a Cartan distance metric:
Measures how far a triple lies from the canonical CNOT location in the Weyl chamber
The gate returned is the B gate, a relatively recent and well-studied quantum gate known for its minimality and efficiency.
Conclusion
Conclusion
The project in deriving the B gate, the most powerful and efficient universal two-qubit gate in the set studied. It is the closest gate to the canonical CNOT point in Cartan coordinates, which means it needs the least amount of entangling resources to achieve universality. This makes it highly practical for implementing any two-qubit operation with minimal overhead.The B gate’s matrix includes complex i terms in its off-diagonal elements, which give it strong entangling capabilities. These terms allow the gate to create maximal entanglement from certain input states. Maximal entanglement is essential for quantum algorithms and processes that rely on quantum correlations.
When decomposed into basic gates like CNOT and single-qubit rotations, the B gate typically requires fewer total gates and results in shallower circuits. This reduction in gate count and circuit depth improves performance on real quantum devices by lowering noise and error accumulation during execution.
This gate can be used as a native gate on quantum hardware to optimize circuit compilation. Implementing the B gate directly can lead to faster quantum computations since it closely approximates the ideal entangling gate needed for universal control over two qubits.
In conclusion, the B gate stands out as the most efficient universal two-qubit gate, combining strong entangling power with minimal resource requirements. It offers a clear advantage for building practical, high-fidelity quantum circuits and advancing the development of scalable quantum computing. Just as the NAND gate forms the backbone of classical universality, able to construct all logic from a single operation, the B gate completes a similar full cycle in the quantum realm. It serves as a compact, entanglement-efficient building block from which all two-qubit operations can be derived. This parallel highlights how, in both classical and quantum computation, the discovery of a minimal, universal gate fundamentally reshapes how we build and optimize computational systems.
When decomposed into basic gates like CNOT and single-qubit rotations, the B gate typically requires fewer total gates and results in shallower circuits. This reduction in gate count and circuit depth improves performance on real quantum devices by lowering noise and error accumulation during execution.
This gate can be used as a native gate on quantum hardware to optimize circuit compilation. Implementing the B gate directly can lead to faster quantum computations since it closely approximates the ideal entangling gate needed for universal control over two qubits.
In conclusion, the B gate stands out as the most efficient universal two-qubit gate, combining strong entangling power with minimal resource requirements. It offers a clear advantage for building practical, high-fidelity quantum circuits and advancing the development of scalable quantum computing. Just as the NAND gate forms the backbone of classical universality, able to construct all logic from a single operation, the B gate completes a similar full cycle in the quantum realm. It serves as a compact, entanglement-efficient building block from which all two-qubit operations can be derived. This parallel highlights how, in both classical and quantum computation, the discovery of a minimal, universal gate fundamentally reshapes how we build and optimize computational systems.
Future Work
Future Work
This project establishes a foundation for analyzing universal quantum gates and their efficiencies, but there is ample room for expansion. One important direction is to explore larger gate sets and multi-qubit systems, moving beyond two-qubit gates to tackle the scalability challenges essential for practical quantum computing. Additionally, incorporating noise models and error correction into gate synthesis and optimization would bring the work closer to real-world conditions by accounting for decoherence and operational imperfections. Another promising avenue is the development of automated synthesis algorithms that leverage machine learning or advanced heuristics to minimize gate depth, error rates, and resource overhead, improving gate compilation processes. Finally, investigating alternative universal gate sets beyond the Weyl chamber parametrization could identify more hardware-friendly or specialized gates, which, when combined with circuit-level optimizations, would enhance both theoretical understanding and experimental feasibility. Bridging the gap between mathematical universality, physical efficiency, and fault tolerance remains a rich field for continued research.
Acknowledgements
Acknowledgements
I would like to sincerely thank my mentor, Adam Millar, for his invaluable guidance and support throughout this project. I am also grateful to the Wolfram directors and teaching assistants, whose insights and feedback played a crucial role in shaping my work. I would like to thank my parents for being the reason I am here today.
Works Cited
Works Cited
◼ Barenco, Adriano, et al. “Elementary gates for quantum computation.” Physical Review A, vol. 52, no. 5, 1995, pp. 3457–3467. https://doi.org/10.1103/PhysRevA.52.3457
◼ Bennett, Charles H., and David P. DiVincenzo. “Quantum information and computation.” Nature, vol. 404, 2000, pp. 247–255. https://doi.org/10.1038/35005001
◼ Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010.
◼ Kitaev, Alexei Y. “Quantum computations: algorithms and error correction.” Russian Mathematical Surveys, vol. 52, no. 6, 1997, pp. 1191–1249. https://doi.org/10.1070/RM1997v052n06ABEH002155
◼ Preskill, John. “Quantum computing in the NISQ era and beyond.” Quantum, vol. 2, 2018, Article 79. https://doi.org/10.22331/q-2018-08-06-79
◼ Deutsch, David. “Quantum theory, the Church–Turing principle and the universal quantum computer.” Proceedings of the Royal Society A, vol. 400, no. 1818, 1985, pp. 97–117. https://doi.org/10.1098/rspa.1985.0070
◼ Makhlin, Yuri. “Nonlocal properties of two-qubit gates and mixed states, and the optimization of quantum computations.” Quantum Information Processing, vol. 1, no. 4, 2002, pp. 243–252. https://doi.org/10.1023/A:1022144002391
◼ Shor, Peter W. “Algorithms for quantum computation: Discrete logarithms and factoring.” Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp. 124–134. https://doi.org/10.1109/SFCS.1994.365700
◼ Bravyi, Sergey, and Alexei Kitaev. “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Physical Review A, vol. 71, 2005, 022316. https://doi.org/10.1103/PhysRevA.71.022316
◼ Morozov, A. “Hall Thruster Geometry.” Journal of Applied Physics, 2000. https://www.researchgate.net/publication/337085936_Thomson_scattering_investigations_of_a_low-power_Hall_thruster_in_standard_and_magnetically-shielded_configurations
◼ Bennett, Charles H., and David P. DiVincenzo. “Quantum information and computation.” Nature, vol. 404, 2000, pp. 247–255. https://doi.org/10.1038/35005001
◼ Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2010.
◼ Kitaev, Alexei Y. “Quantum computations: algorithms and error correction.” Russian Mathematical Surveys, vol. 52, no. 6, 1997, pp. 1191–1249. https://doi.org/10.1070/RM1997v052n06ABEH002155
◼ Preskill, John. “Quantum computing in the NISQ era and beyond.” Quantum, vol. 2, 2018, Article 79. https://doi.org/10.22331/q-2018-08-06-79
◼ Deutsch, David. “Quantum theory, the Church–Turing principle and the universal quantum computer.” Proceedings of the Royal Society A, vol. 400, no. 1818, 1985, pp. 97–117. https://doi.org/10.1098/rspa.1985.0070
◼ Makhlin, Yuri. “Nonlocal properties of two-qubit gates and mixed states, and the optimization of quantum computations.” Quantum Information Processing, vol. 1, no. 4, 2002, pp. 243–252. https://doi.org/10.1023/A:1022144002391
◼ Shor, Peter W. “Algorithms for quantum computation: Discrete logarithms and factoring.” Proceedings 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994, pp. 124–134. https://doi.org/10.1109/SFCS.1994.365700
◼ Bravyi, Sergey, and Alexei Kitaev. “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Physical Review A, vol. 71, 2005, 022316. https://doi.org/10.1103/PhysRevA.71.022316
◼ Morozov, A. “Hall Thruster Geometry.” Journal of Applied Physics, 2000. https://www.researchgate.net/publication/337085936_Thomson_scattering_investigations_of_a_low-power_Hall_thruster_in_standard_and_magnetically-shielded_configurations
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Analysis of the completeness and efficiency of quantum and classical gates
by Arnav Shandilya
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3500950
by Arnav Shandilya
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3500950