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

Ученые записки Казанского университета. Серия Физико-математические науки

Квантовое и классическое моделирование ветвящихся программ

Aida Gainutdinova

Published Jan 1, 2009• 0 citations
OpenAlex

Abstract

The paper views a model of branching programs (BP). A model of classical probabilistic BP is considered along with two different models of quantum BP (once-measuring and many time measuring quantum BP). Three different methods of simulation of BPs are presented: method of classical simulation of quantum BPs and two different methods of quantum simulation of probabilistic BPs. Complexity of methods is proved. Comparative analysis of methods is presented.

Related papers

On simulating the quantum and classical branching programs

Aida Gainutdinova

The complexity classes defined on the basis of branching programs are considered. Some basic relations are established between the complexity classes defined by the probabilistic and quantum branching programs (measure-once, as well as measure-many), computing with bounded or unbounded error. To prove these relations, we developed a method of “linear simulation” of a quantum branching program and a method of “quantum simulation” of a probabilistic branching program.

Journal of Applied and Industrial Mathematics•Mar 1, 2007•1 citation

On computational power of classical and quantum branching programs

Farid Mansurovich Ablayev

We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 24, 2006•1 citation

Classical Simulation Complexity of Quantum Branching Programs

Farid Mansurovich Ablayev

We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width $w$ that computes a function with error $delta$ we present a classical deterministic branching program of the same length and width at most $(1+2/(1-2delta))^{2w}$ that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.

Language and Automata Theory and Applications•Jan 1, 2008•0 citations

Способ организации ветвления в квантовых вычислениях

Vyacheslav F. Guzik, С. М. Гушанский, Евсеев Олег Константинович

Quantum computation can be used to solve NP-tasks, but it does not allow using classical manner of algorithmic organization of the solving task. The offered article describes a method of enhancing the abilities of quantum computations process by adding the fourth step to its three ordinary steps (initialization, computation, measurement. A variant of the adding the step of analysis of temporarily saved state of the system and branching the program of controlling influences comparatively to its result is considered.

Известия Южного федерального университета. Технические науки•Jan 1, 2008•0 citations

Statistical analysis of barren plateaus in variational quantum algorithms

Le Bin Ho, Jesus Urbaneja, Sahel Ashhab

We investigate the barren plateau (BP) phenomenon in variational quantum algorithms using a statistical approach. Using Gaussian function models, we identify three distinct types of BPs. The first type, which we called localized-dip BPs, occurs in landscapes that are mostly flat but contain a dip point where the gradient is large in a small region around the minimum. The second type, called localized-gorge BPs, which are somewhat similar to the localized-dip BPs but contain a gorge line. The third type, called everywhere-flat BPs, appears when the entire landscape is uniformly flat with almost vanishing gradients, making optimization significantly more difficult. After illustrating these behaviors in the Gaussian function models, we extend the analysis to the variational quantum eigensolver (VQE). We consider two types of ansätze: the hardware-efficient ansatz and the random Pauli ansatz. For both ansätze, we only observe the everywhere-flat BPs. Using our statistical approach, we searched for localized-dip and localized-gorge BPs but found no evidence of such features in the examples studied, suggesting that everywhere-flat BPs dominate in these ansätze. Our method effectively probes landscape features by capturing the gradient scaling across parameter space, making it a useful tool for diagnosing BPs in variational algorithms. To mitigate BPs in the VQE, we employ a genetic algorithm (GA) to optimize the random gates generated in the ansätze, thereby reshaping the cost function landscape to enhance the optimization efficiency. A comparison with an unoptimized ansatz shows how the ansatz design can improve the scalability and reliability of variational quantum algorithms.

arXiv:2508.08915•Aug 12, 2025•0 citations

Физические основы и проблемы технической реализации квантового компьютера

Вахний Татьяна Владимировна, Гуц Александр Константинович

The review of different approaches to creation of the quantum computer is given. The main problems of technical realization and prospect of each of approaches are discussed. It is paid attention to researches of behavior of quantum computers by means of the simulators which are based on classical computers.

Matematičeskie struktury i modelirovanie•Jan 1, 2011•0 citations
The paper views a model of branching programs (BP). A model of classical probabilistic BP is considered along with two different models of quantum BP (once-measuring and many time measuring quantum BP). Three different methods of simulation of BPs are presented: method of classical simulation of quantum BPs and two different methods of quantum simulation of probabilistic BPs. Complexity of methods is proved. Comparative analysis of methods is presented.
We present a classical stochastic simulation technique of quantum Branching programs. This technique allows to prove the following relations among complexity classes: PrQP-BP &subuline; PP-BP and BQP-BP &subuline; PP-BP. Here BPP-BP and PP-BP stands for the classes of functions computable with bounded error and unbounded error respectively by stochastic branching program of polynomial size. BQP-BP and PrQP-BP stands the classes of functions computable with bounded error and unbounded error respectively by quantum branching program of polynomial size. Second. We present two different types, of complexity lower bounds for quantum nonuniform automata (OBDDs). We call them "metric" and "entropic" lower bounds in according to proof technique used. We present explicit Boolean functions that show that these lower bounds are tight enough. We show that when considering "almost all Boolean functions" on n variables our entropic lower bounds gives exponential (2c(δ)(n-log n)) lower bound for the width of quantum OBDDs depending on the error δ allowed.
We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width www that computes a function with error deltadeltadelta we present a classical deterministic branching program of the same length and width at most (1+2/(1−2delta))2w(1+2/(1-2delta))^{2w}(1+2/(1−2delta))2w that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.
Quantum computation can be used to solve NP-tasks, but it does not allow using classical manner of algorithmic organization of the solving task. The offered article describes a method of enhancing the abilities of quantum computations process by adding the fourth step to its three ordinary steps (initialization, computation, measurement. A variant of the adding the step of analysis of temporarily saved state of the system and branching the program of controlling influences comparatively to its result is considered.
We investigate the barren plateau (BP) phenomenon in variational quantum algorithms using a statistical approach. Using Gaussian function models, we identify three distinct types of BPs. The first type, which we called localized-dip BPs, occurs in landscapes that are mostly flat but contain a dip point where the gradient is large in a small region around the minimum. The second type, called localized-gorge BPs, which are somewhat similar to the localized-dip BPs but contain a gorge line. The third type, called everywhere-flat BPs, appears when the entire landscape is uniformly flat with almost vanishing gradients, making optimization significantly more difficult. After illustrating these behaviors in the Gaussian function models, we extend the analysis to the variational quantum eigensolver (VQE). We consider two types of ansätze: the hardware-efficient ansatz and the random Pauli ansatz. For both ansätze, we only observe the everywhere-flat BPs. Using our statistical approach, we searched for localized-dip and localized-gorge BPs but found no evidence of such features in the examples studied, suggesting that everywhere-flat BPs dominate in these ansätze. Our method effectively probes landscape features by capturing the gradient scaling across parameter space, making it a useful tool for diagnosing BPs in variational algorithms. To mitigate BPs in the VQE, we employ a genetic algorithm (GA) to optimize the random gates generated in the ansätze, thereby reshaping the cost function landscape to enhance the optimization efficiency. A comparison with an unoptimized ansatz shows how the ansatz design can improve the scalability and reliability of variational quantum algorithms.