arXiv:1708.07429

Quantum Pascal's Triangle and Sierpinski's carpet

Tom Bannink, Harry Buhrman

Published Aug 24, 2017• 4 citations

Abstract

In this paper we consider a quantum version of Pascal's triangle. Pascal's triangle is a well-known triangular array of numbers and when these numbers are plotted modulo 2, a fractal known as the Sierpinski triangle appears. We first prove the appearance of more general fractals when Pascal's triangle is considered modulo prime powers. The numbers in Pascal's triangle can be obtained by scaling the probabilities of the simple symmetric random walk on the line. In this paper we consider a quantum version of Pascal's triangle by replacing the random walk by the quantum walk known as the Hadamard walk. We show that when the amplitudes of the Hadamard walk are scaled to become integers and plotted modulo three, a fractal known as the Sierpinski carpet emerges and we provide a proof of this using Lucas's theorem. We furthermore give a general class of quantum walks for which this phenomenon occurs.

DOI: 10.48550/arxiv.1708.07429

Related papers

Pascal’s Triangle Fractal Symmetries

Nayan E. Myerson-Jain, Shang Liu, Wenjie Ji +2 more

We introduce a model of interacting bosons exhibiting an infinite collection of fractal symmetries-termed "Pascal's triangle symmetries"-which provides a natural U(1) generalization of a spin-(1/2) system with Sierpinski triangle fractal symmetries introduced in Newman et al., [Phys. Rev. E 60, 5068 (1999).PLEEE81063-651X10.1103/PhysRevE.60.5068]. The Pascal's triangle symmetry gives rise to exact degeneracies, as well as a manifold of low-energy states which are absent in the Sierpinski triangle model. Breaking the U(1) symmetry of this model to Z_{p}, with prime integer p, yields a lattice model with a unique fractal symmetry which is generated by an operator supported on a fractal subsystem with Hausdorff dimension d_{H}=ln(p(p+1)/2)/lnp. The Hausdorff dimension of the fractal can be probed through correlation functions at finite temperature. The phase diagram of these models at zero temperature in the presence of quantum fluctuations, as well as the potential physical construction of the U(1) model, is discussed.

arXiv:2110.02237Physical Review LettersMar 14, 202213 citations

Spatial Search on Sierpinski Carpet Using Quantum Walk

Shu Tamegai, Shohei Watabe, Tetsuro Nikuni

We investigate a quantum spatial search problem on a fractal lattice. A recent study for the Sierpinski gasket and tetrahedron made a conjecture that the dynamics of the search on a fractal lattice is determined by spectral dimension. We tackle this problem for the Sierpinski carpet, and our simulation result supports the conjecture. We also propose a scaling hypothesis of oracle calls for the quantum amplitude amplification.

arXiv:1804.06549Journal of the Physical Society of JapanJul 23, 20186 citations

Open Quantum RandomWalks and the Open Quantum Pascal Triangle

Francesco Petruccione, Ilya Sinayskiy

Open Quantum Random Walks (OQRW) were introduced as completely positive maps on an appropriate Hilbert space. The OQRW on the line is shown to give raise to a non-classical Pascal triangle, that stresses the rich dynamical behavior of these walks. Implications and further applications of the OQRW are discussed.

International Conference on Quantum InformationJan 1, 20113 citations

Scaling hypothesis of a spatial search on fractal lattices using a quantum walk

Rei Sato, Tetsuro Nikuni, Shohei Watabe

A quantum spatial search problem on fractal lattices, such as Sierpinski carpets and Menger sponges, is studied numerically. The results confirmed various conjectures on the relationship between the number of oracle calls needed for a search with respect to the number of sites and spatial dimensions.

arXiv:1908.11827Physical Review AFeb 10, 20209 citations

QUANTUM RANDOM WALK ON FRACTALS

Kai Zhao

Quantum walks are the quantum mechanical analogue of classical random walks. Discrete-time quantum walks have been introduced and studied mostly on the line Z or higher dimensional space Z d but rarely defined on graphs with fractal dimensions because the coin operator depends on the position and the Fourier transform on the fractals is not defined. Inspired by its nature of classical walks, different quantum walks will be defined by choosing different shift and coin operators. When the coin operator is uniform, the results of classical walks will be obtained upon measurement at each step. Moreover, with measurement at each step, our results reveal more information about the classical random walks. In this dissertation, two graphs with fractal dimensions will be considered. The first one is Sierpinski gasket, a degree-4 regular graph with Hausdorff di- mension of df = ln 3/ ln 2. The second is the Cantor graph derived like Cantor set, with Hausdorff dimension of df = ln 2/ ln 3. The definitions and amplitude functions of the quantum walks will be introduced. The main part of this dissertation is to derive a recursive formula to compute the amplitude Green function. The exiting probability will be computed and compared with the classical results. When the generation of graphs goes to infinity, the recursion of the walks will be investigated and the convergence rates will be obtained and compared with the classical counterparts.

Jan 1, 20180 citations

Six Exceptional Properties of the "Perez Hourglass": Perspectives toward New Types of Artificial Intelligence and Quantum Computers

Perez, Jean claude

Abstract More than thirty-five years after the first intuitions linking self-organization, neuronal networks and the golden ratio (Perez, 1988), a remarkable numerical structure has finally emerged from the depths of Pascal’s triangle: the “Perez Hourglass”. This fractal, self-similar pattern, simultaneously antimatter of the famous Pascal triangle and digital incarnation of the Fibonacci sequence (OEIS A000975), reveals a perfect hourglass-shaped distribution of parity across the rows of the binomial triangle when analyzed through a specific recursive filtering method. Here we demonstrate for the first time that this structure is not merely a mathematical curiosity but constitutes an ideal topological substrate for a radically new generation of quantum computers: fractal quantum computers based on the Hourglass attractor. In Appendix, we present the first rigorous formulation of a quantum computing architecture whose topological backbone is the recently discovered “Perez Hourglass” fractal attractor embedded in Pascal’s triangle modulo 2 (Perez, 2025a,b). The Hourglass defines a family of sparse, exactly self-similar qubit lattices whose connectivity graph is governed by Fibonacci numbering and whose bond angles are multiples of the golden angle 2πφ⁻². We prove that this geometry yields: 1/ a distance-3 CSS quantum code with parameters [[F_{2n+1}, 1, F_n]] exceeding the Bravyi-Poulin-Terhal bound, 2/ native implementation of golden-phase gates e^{iπφ⁻²} that are optimal for quadratic speedup in quantum phase estimation, 3/ magic-state distillation factories with overhead reduced to O(log log N).Full open-source implementations in Qiskit, Cirq, and Quantify are provided.

Nov 25, 20250 citations