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:1708.07429

Quantum Pascal's Triangle and Sierpinski's carpet

Tom Bannink, Harry Buhrman

Published Aug 24, 2017• 10 citations
arXivHTMLPDF

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.02237•Physical Review Letters•Mar 14, 2022•14 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.06549•Journal of the Physical Society of Japan•Jul 23, 2018•7 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 Information•Jan 1, 2011•3 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.11827•Physical Review A•Feb 10, 2020•9 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, 2018•0 citations

Quantum criticality from Ising model on fractal lattices

Beni Yoshida, Aleksander Kubica

We study the quantum Ising model on the Sierpiński triangle, whose Hausdorff dimension is $\log 3/ \log 2 \approx 1.585$, and demonstrate that it undergoes second-order phase transition with scaling relations satisfied precisely. We also study the quantum $3$-state Potts model on the Sierpiński triangle and find first-order phase transition, which is consistent with a prediction from $ε$-expansion that the transition becomes first-order for $D > 1.3$. We then compute critical exponents of the Ising model on higher-dimensional Sierpiński pyramids with various Hausdorff dimension via Monte-Carlo simulations and real-space RG analysis for $D\in[1,3]$. We find that only the correlation length exponent $ν$ interpolates the values of integer-dimensional models. This implies that, contrary to a generally held belief, the universality class of quantum phase transition may not be uniquely determined by symmetry and spatial dimension of the system. This work initiates studies on quantum critical phenomena on graphs and networks which may be of significant importance in the context of quantum networks and communication.

arXiv:1404.6311•Apr 25, 2014•19 citations
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.
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.
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.
We study the quantum Ising model on the Sierpiński triangle, whose Hausdorff dimension is log⁡3/log⁡2≈1.585\log 3/ \log 2 \approx 1.585log3/log2≈1.585, and demonstrate that it undergoes second-order phase transition with scaling relations satisfied precisely. We also study the quantum 333-state Potts model on the Sierpiński triangle and find first-order phase transition, which is consistent with a prediction from εεε-expansion that the transition becomes first-order for D>1.3D > 1.3D>1.3. We then compute critical exponents of the Ising model on higher-dimensional Sierpiński pyramids with various Hausdorff dimension via Monte-Carlo simulations and real-space RG analysis for D∈[1,3]D\in[1,3]D∈[1,3]. We find that only the correlation length exponent ννν interpolates the values of integer-dimensional models. This implies that, contrary to a generally held belief, the universality class of quantum phase transition may not be uniquely determined by symmetry and spatial dimension of the system. This work initiates studies on quantum critical phenomena on graphs and networks which may be of significant importance in the context of quantum networks and communication.