ValueError: Operation doesn't satisfy the given `keep` but can't be decomposed

Question

I was going through Cirq tutorial on Shor's algorithm and was able to implement it successfully using cirq. But it takes forever to run for any n > 21; so I tried to use the qsim simulator instead of using cirq.

What I tried to do -

I replaced measurement = cirq.sample(circuit) with measurement = simulator.simulate(circuit).

def quantum_order_finder(x: int, n: int) -> Optional[int]:
    if x < 2 or n <= x or math.gcd(x, n) > 1:
        raise ValueError(f'Invalid x={x} for modulus n={n}.')

    circuit = make_order_finding_circuit(x, n)
    
    simulator = qsimcirq.QSimSimulator()
    measurement = simulator.simulate(circuit)
    
    return process_measurement(measurement, x, n)

The error I got -

<ipython-input-21-b2e4008cd3ca> in quantum_order_finder(x, n)
     22
---> 23     measurement = simulator.simulate(circuit)
     24

/usr/local/lib/python3.7/dist-packages/cirq/sim/simulator.py in simulate(self, program, param_resolver, qubit_order, initial_state)
    517         """
    518         return self.simulate_sweep(
--> 519             program, study.ParamResolver(param_resolver), qubit_order, initial_state
    520         )[0]
    521 

/usr/local/lib/python3.7/dist-packages/qsimcirq/qsim_simulator.py in simulate_sweep(self, program, params, qubit_order, initial_state)
    561                 solved_circuit,
    562                 translator_fn_name,
--> 563                 cirq_order,
    564             )
    565             options["s"] = self.get_seed()

/usr/local/lib/python3.7/dist-packages/qsimcirq/qsim_simulator.py in _translate_circuit(self, circuit, translator_fn_name, qubit_order)
    858         if translated_circuit is None:
    859             translator_fn = getattr(circuit, translator_fn_name)
--> 860             translated_circuit, moment_indices = translator_fn(qubit_order)
    861             self._translated_circuits.append(
    862                 (circuit, translated_circuit, moment_indices)

/usr/local/lib/python3.7/dist-packages/qsimcirq/qsim_circuit.py in translate_cirq_to_qsim(self, qubit_order)
    316             ops_by_gate = [
    317                 cirq.decompose(op, fallback_decomposer=to_matrix, keep=has_qsim_kind)
--> 318                 for op in moment
    319             ]
    320             moment_length = max((len(gate_ops) for gate_ops in ops_by_gate), default=0)

/usr/local/lib/python3.7/dist-packages/qsimcirq/qsim_circuit.py in <listcomp>(.0)
    316             ops_by_gate = [
    317                 cirq.decompose(op, fallback_decomposer=to_matrix, keep=has_qsim_kind)
--> 318                 for op in moment
    319             ]
    320             moment_length = max((len(gate_ops) for gate_ops in ops_by_gate), default=0)

/usr/local/lib/python3.7/dist-packages/cirq/protocols/decompose_protocol.py in decompose(val, intercepting_decomposer, fallback_decomposer, keep, on_stuck_raise, preserve_structure)
    245                 error = on_stuck_raise(item)
    246                 if error is not None:
--> 247                     raise error
    248 
    249         output.append(item)

ValueError: Operation doesn't satisfy the given `keep` but can't be decomposed: <__main__.ModularExp object at 0x7efe3c3e76d0>

Is there a difference between simulate(circuit) and sample(circuit) ? And if so, then how do i make the algorithm run with qismcirq instead of cirq ?

Answer 1

The issue is that the ArithmeticOperation class defined in the tutorial doesn't define a _decompose_ method. qsim is based on decomposing things into 2 qubit operations, but there's no specified way to turn this operation into simpler operations.

I think you have two options:

1. Open an issue against qsim to natively support permutations, such as yours, that are specified by the cirq.ArithmeticOperation class. I think "because then it would work on the Shor's algorithm tutorial" is a reasonably compelling argument. This isn't a lot of work on your end but kinda leaves you in limbo until the qsim devs either accept and complete the issue or else decide not to do it.

2. Add a _decompose_ method that turns the modular exponentiation into modular multiplications. And give them a decompose method into modular additions. And give them a decompose method into Toffolis. This is a lot of work but you'll learn about building circuits.