Quantum games for finding multiple counterfeit coins

[rraymondhp]

Abstract

Given a k > 1 counterfeit coins (all of the same weight lighter than true coins) among n >> k coins, devise a quantum algorithm that uses a quantum balance, to weigh coins and identify which subset of coins is lighter, to identify all k counterfeit coins.

Original Description

The algorithm for k = 1 counterfeit coin is already implemented in the qiskit-community-tutorial, as here. To develop a quantum algorithm with multiple counterfeit coins, one has to combine the quantum amplitude amplification with the basic algorithm for k = 1 counterfeit coin, as well as implementing the quantum weighing oracle. All the functionalities are already available from qiskit-aqua. The quantum algorithm is shown here.

The quantum algorithm achieves a quartic speedup against the best known classical algorithm

Final Description

Given M coins among which k are counterfeits, classical algorithm need to query a balance (oracle) $\Omega(k\log{(N/k)})$ times while a proper quantum algorithm requires only $\Omega(\log{N})$ times, which is independent of the coin number N.

We verify the quantum algorithm provided by the jupyter notebook can deal with k=1 with only 1 query. Then we attempt to extend to k>2. Instead of using the Iwama et al. algorithm, in this hackathon, we attmpt to extend the provided algorithm by redesigning the oracle. Specifically, we create a super-oracle which return balance as long as there is one case in the permutation of the given coins are balance, and tilde otherwise. This essentially rules out the given coins with even number of false coin and reduce the problem to the situation with odd false coins, where the original algorithm provides a good generalization. Moreover, the change to the circuit is simply changing the logic to apply XOR to all false coins, which is simple while correct. We should our proposed algorithm is theoratically sound.

The problem of our simple extension is that we are not fully embracing the power of quantum computing and need to query the oracle too many times.

Moreover, the tutorial notebook exists a bug such that the false coin cannot appear at position M-1. We identify the problem and fix the bug. The tutorial will be updated.

Members

• Wen Jun, @wenjunsa11c
• Hang Weiqiang
• Li Guodong
• Oujang Kun
• Kelvin Loh
• Salamat, @salamatburj
• Qiskit Coach: @rraymondhp - Slack:@rudyhar email: rraymondhp@gmail.com

Deliverable

A tutorial and possibly an app?

GitHub repo

[kunrenzhilu]

I want to work on it

[wenjunsa11c]

Hi Ruby, I'd like to join, can I? Thank you.

[lguodongnus]

I am in, my name is LI GUODONG

[lguodongnus]

Hi Ruby, I'd like to join, can I? Thank you. Are you in slack, what's your slack name

[hangweiqiang-uestc]

Hi, Rudy. I'd like to join.

[kunrenzhilu]

Given M coins among which k are counterfeits, classical algorithm need to query a balance (oracle) $\Omega(k\log{(N/k)})$ times while a proper quantum algorithm requires only $\Omega(\log{N})$ times, which is independent of the coin number N.

We verify the quantum algorithm provided by the jupyter notebook can deal with k=1 with only 1 query. Then we attempt to extend to k>2. Instead of using the Iwama et al. algorithm, in this hackathon, we attmpt to extend the provided algorithm by redesigning the oracle. Specifically, we create a super-oracle which return balance as long as there is one case in the permutation of the given coins are balance, and tilde otherwise. This essentially rules out the given coins with even number of false coin and reduce the problem to the situation with odd false coins, where the original algorithm provides a good generalization. Moreover, the change to the circuit is simply changing the logic to apply XOR to all false coins, which is simple while correct. We should our proposed algorithm is theoratically sound.

The problem of our simple extension is that we are not fully embracing the power of quantum computing and need to query the oracle too many times.

Moreover, the tutorial notebook exists a bug such that the false coin cannot appear at position M-1. We identify the problem and fix the bug. The tutorial will be updated.

[HuangJunye]

@kunrenzhilu Thanks for writing the description. Can you send me the link to your github repo for the project?