Integrated Quantum-Walk Structure and NAND Tree on a Photonic Chip

In the age of the post-Moore era, the next-generation computing model would be a hybrid architecture consisting of different physical components, such as photonic chips. In 2008, it was proposed that the solving of the NAND-tree problem can be sped up by quantum walk. This scheme is groundbreaking due to the universality of the NAND gate. However, experimental demonstration has not been achieved so far, mostly due to the challenge in preparing the propagating initial state. Here we propose an alternative solution by including a structure called a ``quantum slide,'' where a propagating Gaussian wave packet can be generated deterministically along a properly engineered chain. In our experimental demonstration, the optical NAND tree is capable of solving computational problems with a total of four input bits, based on the femtosecond laser 3D direct-writing technique on a photonic chip. These results remove one main roadblock to photonic NAND-tree computation, and the construction of a quantum slide may find other interesting applications in quantum information and quantum optics.