# Solving simultaneous multiple chinese remainder theorem on the quantum computer - possible?

Is it possible to solving simultaneous multiple chinese remainder theorem on the quantum computer?

We have $k$ variables. Each variable can take two values.

The question is: can we calculate all possible circuits equations chinese remainder theorem (which may be $2^k$) and reduce to the smallest result on a quantum computer?

I know the question can be very difficult but I wanted to ask.

I hope I have described the problem quite clearly (but maybe there are ambiguities).

For example we have table:

2 3 7 31

A B C D => [RESULT]

0 1 3 4 => 934
0 1 3 27 => 430
0 1 4 4 => 4
0 1 4 27 => 802
0 2 3 4 => 500
0 2 3 27 => 1298
0 2 4 4 => 872
0 2 4 27 => 368


Third line:

0 1 3 4 => 934


means the system of equations:

$x \equiv 0 \pmod 2$

$x \equiv 1 \pmod 3$

$x \equiv 3 \pmod 7$

$x \equiv 4 \pmod {31}$

and solution for this line in CRT (chinese remainder theorem) is 934.

The final result that the algorithm should return (minimum) is 4. This result is in line:

0 1 4 4 => 4


This is just an example - I wanted to show to know what I mean.

Someone may have some idea?

Sorry for the (maybe) difficult question.

## 1 Answer

If you prepare a superposition containing the various input problems, a quantum computer will allow you to compute a superposition containing the various outputs.

That being said, I'm not sure why you would want to do this. You only get to sample one of the outputs, and you don't get to pick which one. You'll get one of them at random. Presumably you would instead do some quantum computation on the output superposition, perhaps use a QFT to sample from their frequency space... but just remember that this means you must erase the input! Otherwise you won't be able to interfere the various output cases.