A graph-colouring search uses qubits

PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms

Quantum Information and Technology, Ch Grover search, amplitude amplification and counting

Problem

A graph-colouring search uses n=8n = 8 qubits, so N=28=256N = 2^8 = 256 candidate colourings. ((a)) Using the same Cn−1(Z)C^{n-1}(Z)-inside-X⊗nX^{\otimes n} construction for the diffusion operator (with m−1m-1 ancillas and 2(m−1)2(m-1) Toffoli gates for an mm-control gate), state the number of ancilla qubits and Toffoli gates needed for n=8n = 8. ((b)) An estimate suggests the search has M=16M = 16 correctly coloured graphs, but the true value might be M=17M = 17. Using the counting-register rule 2t≥4πMN2^t \ge 4\pi\sqrt{MN} with M=16M = 16, find the smallest register size tt needed to tell M=16M = 16 apart from M=17M = 17, and the number of oracle queries this costs.

Browse the problem library