I would like to know if it is possible to construct a set of quantum gates to do the following:

  • Start with a set of N qubits representing a number expressed in binary notation.
  • The values in the various qubits are entangled in unknown ways with each other, and have unknown ratios of likelihood of being 1 or 0.
  • calculate a new qubit whose probability of being 1 is the probability that the number represented by the N qubits exceeds $\delta$, where $\delta$ is an externally provided (classical) parameter.

The objective is to create a quantum algorithm for general purpose optimization.


You need to disambiguate what you mean by "calculate a qubits whose probability of being 1 is...". Is the qubit allowed to be entangled with the others? What phase is it supposed to have?

It sounds like you're just describing an arithmetic less-than comparison. A simple way to do it is to use an adder. Take your two n-qubit inputs and run them through an n+1 qubit subtractor, then run the bottom n qubits through an n bit adder. The extra qubit that came out of the subtractor is the carry overflow and contains the result of the comparison.

  • $\begingroup$ I tkink the output qbit must necessarily be entangled with the N qbits. The subtractor->adder sounds like a good approach. But it wouldn't act on two sers of qbits; it would act on one set of qbits and a classical set representing $\delta$. $\endgroup$ – S. McGrew Mar 18 at 15:41
  • $\begingroup$ @S.McGrew Just load the classical value into a quantum register temporarily. Because the circuit is a classical reversible circuit, and because that classical circuit doesn't mutate the value you loaded, it won't get entangled with the result so it's safe to measure the temp value out afterward. $\endgroup$ – Craig Gidney Mar 18 at 16:18
  • $\begingroup$ Check. That is very helpful. $\endgroup$ – S. McGrew Mar 18 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.