def _run(qc, shots):
  simulator = AerSimulator()
  tqc = transpile(qc, simulator, optimization_level=3)

  job = simulator.run(tqc, shots=shots)
  result = job.result()

  return dict(sorted(result.get_counts().items()))

Fedoriaka implements the \(MAJ\) and \(MAJ^{-1}\) gates efficiently by incorporating the \(AND\) and \(AND^{-1}\) gates described in “Halving the cost of quantum addition” (Gidney). Below is the implementation of said gates.

Screenshot 2026-04-09 224839.png

The \(AND^{-1}\) implementation is particularly unique as it uses classical measurement to skip practically every expensive operation used in the \(AND\) implementation. The phase is preserved by a \(CZ\) controlled on the result of the measurement.

Testing \(AND\) and \(AND^{-1}\)

qc = QuantumCircuit(3,3)
qc.h(2)
qc.t(2)
qc.x(0)
qc.x(1)
qc.compose(_AND(), qubits=[0,1,2], inplace=True)
qc.measure([0,1,2], [0,1,2])
assert _run(qc,8) == {'111': 8}, "AND gate does not work correctly"

qc = QuantumCircuit(3,3)
qc.h(2)
qc.t(2)
qc.x(0)
qc.compose(_AND(), qubits=[0,1,2], inplace=True)
qc.compose(_ANDdg(), qubits=[0,1,2], clbits=[0], inplace=True)
qc.measure([0,1,2],[0,1,2])
assert _run(qc,8) == {'001': 8}, "ANDdg fails to undo AND gate"
def _AdderBlock(constant_bit):
  qc = QuantumCircuit(3)
  if constant_bit:
    qc.x(0)
    qc.x(1)
  qc.append(_AND(), [0,1,2])
  if constant_bit:
    qc.x(2)
  return qc.to_gate(label='add_block')


def _AdderBlockUncompute_op(constant_bit):
  qc = QuantumCircuit(3, 1)
  if constant_bit:
    qc.x(2)
  qc.compose(_ANDdg(), qubits=[0,1,2], clbits=[0], inplace=True)
  if constant_bit:
    qc.x(0)
  qc.cx(0,1)

  return qc

Algorithmically generalized implementation, following the fully-optimized Adder Design from the paper, shown below: image.png

Fedoriaka Adder Export

FedoriakaConstantAdder


def FedoriakaConstantAdder(
    constant:int, size:int
)->QuantumCircuit:

Implements |b> -> |(b + a) mod 2^N> v Where a is a fixed classical constant Via the method outlined in: “New Circuit for Quantum Adder by Constant” (Dmytro Fedoriaka)

Args: constant (int): Fixed classical value to add, where 0 <= constant < 2^size a size (int): Number of qubits in the register b (0<size)

Result: QuantumCircuit object implementing in-place constant addition Takes size-3 additional ancillae qubits (or 0 for size<4) and 1 classical bit (used in uncomputation through venting) Can be applied to circuits via .compose() - .append() will not work

Circuit Register Layout: [ input_qubits | ancillae_qubits ] [ venting_clbit ]

Testing Fedoriaka Adder

qc = QuantumCircuit(2,2)
qc.x(1)
qc.compose(FedoriakaConstantAdder(3,2), qubits=[0,1])
qc.measure([0,1], [0,1])
assert _run(qc,8) == {'10': 8}, "ConstantAdder_Size2 does not work correctly"

qc = QuantumCircuit(5,4)
qc.x(0)
qc.x(1)
qc.compose(FedoriakaConstantAdder(5,4), qubits=[0,1,2,3,4], clbits=[0], inplace=True)
qc.measure([0,1,2,3], [0,1,2,3])
assert _run(qc,8) == {'1000': 8}

qc = QuantumCircuit(7,5)
qc.compose(FedoriakaConstantAdder(6,5), qubits=[0,1,2,3,4,5,6], clbits=[0], inplace=True)
qc.compose(FedoriakaConstantAdder(2,5), qubits=[0,1,2,3,4,5,6], clbits=[0], inplace=True)
qc.measure([0,1,2,3,4], [0,1,2,3,4])
assert _run(qc,8) == {'01000': 8}

Generalizing the Control-Adder design shown in the paper: image.png

Controlled Fedoriaka Adder Export

Controlled_FedoriakaConstantAdder


def Controlled_FedoriakaConstantAdder(
    constant, size
):

Implements |c>|b> -> |c>|(b + ca) mod 2^N>* Where a is a fixed classical constant and c is a quantum control bit Via the method for a controlled-adder outlined in: “New Circuit for Quantum Adder by Constant” (Dmytro Fedoriaka)

Args: constant (int): Fixed classical value to add, where 0 <= constant < 2^size a size (int): Number of qubits in the register b (0<size)

Result: QuantumCircuit object implementing in-place controlled constant addition Takes 1 control bit, size-2 additional ancillae qubits (or 0 for size<3), and 1 classical bit (used in uncomputation through venting) Can be applied to circuits via .compose() - .append() will not work

Circuit Register Layout: [ control_qubit | input_qubits | ancillae_qubits ] [ venting_clbit ]

Testing Controlled Fedoriaka Adder

qc = QuantumCircuit(3,2)
qc.x(0) #control on
qc.compose(Controlled_FedoriakaConstantAdder(2,2), qubits=[0,1,2], inplace=True)
qc.measure([1,2], [0,1])
assert _run(qc,8) == {'10': 8}, "Controlled_ConstantAdder_Size2 does not add properly"

qc = QuantumCircuit(3,2)
#control off
qc.compose(Controlled_FedoriakaConstantAdder(2,2), qubits=[0,1,2])
qc.measure([1,2], [0,1])
assert _run(qc,8) == {'00': 8}, "Controlled_ConstantAdder_Size2 is not disabeled by control qubit"

qc = QuantumCircuit(7,4)
#control off
qc.compose(Controlled_FedoriakaConstantAdder(15,4), qubits=[6,0,1,2,3,4,5], clbits=[0], inplace=True)
qc.measure([1,2,3,4], [0,1,2,3])
assert _run(qc,8) == {'0000': 8}, "Controlled_ConstantAdder_Size3 is not disabeled by control qubit"

qc = QuantumCircuit(9,5)
qc.x(8)
qc.compose(Controlled_FedoriakaConstantAdder(12,5), qubits=[8,0,1,2,3,4,5,6,7], clbits=[0], inplace=True)
qc.compose(Controlled_FedoriakaConstantAdder(21,5), qubits=[8,0,1,2,3,4,5,6,7], clbits=[0], inplace=True)
qc.measure([0,1,2,3,4], [0,1,2,3,4])
assert _run(qc,8) == {'00001': 8}, "Controlled_ConstantAdder_Size3 does not add properly"