Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0708.1484

A quantum dot implementation of the quantum NAND algorithm

Jacob M. Taylor

Published Aug 10, 2007• 2 citations
arXivHTMLPDF

Abstract

We propose a physical implementation of the quantum NAND tree evaluation algorithm. Our approach, based on continuous time quantum walks, uses the wave interference of a single electron in a heirarchical set of tunnel coupled quantum dots. We find that the query complexity of the NAND tree evaluation does not suffer strongly from disorder and dephasing, nor is it directly limited by temperature or restricted dimensionality for 2-d structures. Finally, we suggest a potential application of this algorithm to the efficient determination of high-order correlation functions of complex quantum systems.

DOI
10.48550/arxiv.0708.1484

Related papers

Discrete-query quantum algorithm for NAND trees

Andrew M. Childs, Richard Cleve, Stephen P. Jordan +1 more

Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating nand trees that runs in time O ( √ N log N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N 1/2+ǫ) queries in the conventional quantum query model, for any fixed ǫ> 0. A nand tree of depth n is a balanced binary tree whose internal vertices represent nand gates. Placing bits x1,...,x2 n at the leaves, the root of the nand tree evaluates to the function fn(x1,...,x2 n), where fn: {0, 1} 2n → {0, 1} is defined recursively as follows. For n = 0, f0(x) = x, and for n> 0, fn(x1,..., x2 n) = ¬ ( fn−1(x1,..., x 2 n−1) ∧ fn−1(x 2 n−1 +1,...,x2 n)). (1) The goal of the nand tree problem is to evaluate fn(x1,..., x2 n), making as few queries to the bits x1,..., x2 n as possible. The optimal classical randomized algorithm for this problem makes Θ(N 0.753) queries, where N = 2 n [7, 8, 9]. Until now, no better quantum algorithm was known, whereas the best known quantum lower bound is only Ω ( √ N) [1]. Here we show that for any fixed ǫ> 0, the quantum query complexity of evaluating nand trees is O(N 1/2+ǫ).

•Feb 16, 2007•55 citations

A Quantum Algorithm for the Hamiltonian NAND Tree

Edward Farhi, Jeffrey Goldstone, Sam Gutmann

We give a quantum algorithm for the binary NAND tree problem in the Hamiltonian oracle model. The algorithm uses a continuous time quantum walk with a run time proportional to sqrt N. We also show a lower bound of sqrt N for the NAND tree problem in the Hamiltonian oracle model.

arXiv:quant-ph/0702144•Feb 14, 2007•169 citations

Every NAND formula of size N can be evaluated in time N^{1/2+o(1)} on a quantum computer

Andrew M. Childs, Ben W. Reichardt, Robert Špalek +1 more

For every NAND formula of size N, there is a bounded-error N^{1/2+o(1)}-time quantum algorithm, based on a coined quantum walk, that evaluates this formula on a black-box input. Balanced, or ``approximately balanced,'' NAND formulas can be evaluated in O(sqrt{N}) queries, which is optimal. It follows that the (2-o(1))-th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

arXiv:quant-ph/0703015•Mar 2, 2007•50 citations

Continuous-time quantum walks: simulation and application

Josh Izaac

Quantum walks are a fundamental tool in the study of quantum information, bridging the gap between quantum computation and modelling complex systems. In this thesis, we present a software package for simulation of multiparticle continuous-time quantum walks (CTQWs) using high performance computation, and detail a method of systematic dimensionalty reduction for fermionic CTQWs. We then consider CTQW applications; proving that the single particle CTQW is unsuited for determining graph isomorphism, and proposing a CTQW-based network centrality algorithm. This algorithm is utilized in the first successful physical quantum centrality implementation. Finally, we extend our centrality algorithm to PT-symmetric directed graphs.

•Jan 1, 2017•0 citations

Efficient circuit implementation for coined quantum walks on binary trees and application to reinforcement learning

Thomas Mullor, David Vigouroux, Louis Béthune

Quantum walks on binary trees are used in many quantum algorithms to achieve important speedup over classical algorithms. The formulation of this kind of algorithms as quantum circuit presents the advantage of being easily readable, executable on circuit based quantum computers and simulators and optimal on the usage of resources. We propose a strategy to compose quantum circuit that performs quantum walk on binary trees following universal gate model quantum computation principles. We give a particular attention to NAND formula evaluation algorithm as it could have many applications in game theory and reinforcement learning. We therefore propose an application of this algorithm and show how it can be used to train a quantum reinforcement learning agent in a two player game environment.

arXiv:2210.06784•IEEE/ACM Symposium on Edge Computing (SEC)•Dec 1, 2022•2 citations

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

Yao Wang, Zi-Wei Cui, Yong‐Heng Lu +5 more

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.

arXiv:2001.08755•Physical Review Letters•Oct 14, 2020•12 citations
We propose a physical implementation of the quantum NAND tree evaluation algorithm. Our approach, based on continuous time quantum walks, uses the wave interference of a single electron in a heirarchical set of tunnel coupled quantum dots. We find that the query complexity of the NAND tree evaluation does not suffer strongly from disorder and dephasing, nor is it directly limited by temperature or restricted dimensionality for 2-d structures. Finally, we suggest a potential application of this algorithm to the efficient determination of high-order correlation functions of complex quantum systems.
Recently, Farhi, Goldstone, and Gutmann gave a quantum algorithm for evaluating nand trees that runs in time O ( √ N log N) in the Hamiltonian query model. In this note, we point out that their algorithm can be converted into an algorithm using O(N 1/2+ǫ) queries in the conventional quantum query model, for any fixed ǫ> 0. A nand tree of depth n is a balanced binary tree whose internal vertices represent nand gates. Placing bits x1,...,x2 n at the leaves, the root of the nand tree evaluates to the function fn(x1,...,x2 n), where fn: {0, 1} 2n → {0, 1} is defined recursively as follows. For n = 0, f0(x) = x, and for n> 0, fn(x1,..., x2 n) = ¬ ( fn−1(x1,..., x 2 n−1) ∧ fn−1(x 2 n−1 +1,...,x2 n)). (1) The goal of the nand tree problem is to evaluate fn(x1,..., x2 n), making as few queries to the bits x1,..., x2 n as possible. The optimal classical randomized algorithm for this problem makes Θ(N 0.753) queries, where N = 2 n [7, 8, 9]. Until now, no better quantum algorithm was known, whereas the best known quantum lower bound is only Ω ( √ N) [1]. Here we show that for any fixed ǫ> 0, the quantum query complexity of evaluating nand trees is O(N 1/2+ǫ).
Quantum walks are a fundamental tool in the study of quantum information, bridging the gap between quantum computation and modelling complex systems. In this thesis, we present a software package for simulation of multiparticle continuous-time quantum walks (CTQWs) using high performance computation, and detail a method of systematic dimensionalty reduction for fermionic CTQWs. We then consider CTQW applications; proving that the single particle CTQW is unsuited for determining graph isomorphism, and proposing a CTQW-based network centrality algorithm. This algorithm is utilized in the first successful physical quantum centrality implementation. Finally, we extend our centrality algorithm to PT-symmetric directed graphs.
Quantum walks on binary trees are used in many quantum algorithms to achieve important speedup over classical algorithms. The formulation of this kind of algorithms as quantum circuit presents the advantage of being easily readable, executable on circuit based quantum computers and simulators and optimal on the usage of resources. We propose a strategy to compose quantum circuit that performs quantum walk on binary trees following universal gate model quantum computation principles. We give a particular attention to NAND formula evaluation algorithm as it could have many applications in game theory and reinforcement learning. We therefore propose an application of this algorithm and show how it can be used to train a quantum reinforcement learning agent in a two player game environment.
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.