Vishwanathan Akshay
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Vishwanathan Akshay has a total of 14 co-authors. Here are the top co-authors by number of shared publications:
- Jacob Biamonte
Skolkovo Institute of Science and Technology, Moscow 121205, Russia
8 shared publications - Hariphan Philathong
Skolkovo Institute of Science and Technology, Moscow 121205, Russia
5 shared publications - Daniil Rabinovich
Russian Quantum Center
3 shared publications - Ernesto Campos
Skolkovo Institute of Science and Technology
3 shared publications - Igor Zacharov
Skolkovo Institute of Science and Technology
3 shared publications H. Philathong
Skolkovo Institute of Science and Technology, 30 Bolshoy Boulevard, Moscow 121205, Russian Federation
2 shared publications
Latest Publications
- Open Access
- 1 December 2023
- Published by IOP Publishing in Journal of Physics: Complexity
- Vol. 4 (4) , 045010
Computational phase transition signature in Gibbs sampling
Gibbs sampling is fundamental to a wide range of computer algorithms. Such algorithms are set to be replaced by physics based processors—be it quantum or stochastic annealing devices—which embed problem instances and evolve a physical system into a low-energy ensemble to recover a probability distribution. At a critical constraint to variable ratio, satisfiability (SAT) problem instances exhibit a SAT-UNSAT transition (frustrated to frustration free). Algorithms require increasing computational resources from this critical point. This is a so called, algorithmic or computational phase transition and has extensively been studied. In this paper we consider the complexity in sampling and recovering ground states from resultant distributions of a physics based processor. In particular, we first consider the ideal Gibbs distributions at some fixed inverse temperature and observe that the success probability in sampling and recovering ground states decrease for instances starting at the critical density. Furthermore, simulating the Gibbs distribution, we employ Ising spin dynamics, which play a crucial role in understanding of non-equilibrium statistical physics, to find their steady states of 2-SAT Hamiltonians. We observe that beyond the critical density, the probability of sampling ground states decreases. Our results apply to several contemporary devices and provide a means to experimentally probe a signature of the computational phase transition.
- 1 December 2023
- Published by IOP Publishing in Journal of Physics: Complexity
- Vol. 4 (4) , 045010
Open AccessComputational phase transition signature in Gibbs sampling
Gibbs sampling is fundamental to a wide range of computer algorithms. Such algorithms are set to be replaced by physics based processors—be it quantum or stochastic annealing devices—which embed problem instances and evolve a physical system into a low-energy ensemble to recover a probability distribution. At a critical constraint to variable ratio, satisfiability (SAT) problem instances exhibit a SAT-UNSAT transition (frustrated to frustration free). Algorithms require increasing computational resources from this critical point. This is a so called, algorithmic or computational phase transition and has extensively been studied. In this paper we consider the complexity in sampling and recovering ground states from resultant distributions of a physics based processor. In particular, we first consider the ideal Gibbs distributions at some fixed inverse temperature and observe that the success probability in sampling and recovering ground states decrease for instances starting at the critical density. Furthermore, simulating the Gibbs distribution, we employ Ising spin dynamics, which play a crucial role in understanding of non-equilibrium statistical physics, to find their steady states of 2-SAT Hamiltonians. We observe that beyond the critical density, the probability of sampling ground states decreases. Our results apply to several contemporary devices and provide a means to experimentally probe a signature of the computational phase transition.
- 25 October 2022
- Published by American Physical Society (APS) in Physical Review A
- Vol. 106 (4) , 042438
Circuit depth scaling for quantum approximate optimization
Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density—a problem constraint to a variable ratio—induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5–15 qubits.- 25 October 2022
- Published by American Physical Society (APS) in Physical Review A
- Vol. 106 (4) , 042438
Circuit depth scaling for quantum approximate optimization
Variational quantum algorithms are the centerpiece of modern quantum programming. These algorithms involve training parametrized quantum circuits using a classical coprocessor, an approach adapted partly from classical machine learning. An important subclass of these algorithms, designed for combinatorial optimization on current quantum hardware, is the quantum approximate optimization algorithm (QAOA). Despite efforts to realize deeper circuits, experimental state-of-the-art implementations are limited to a fixed depth. However, it is known that problem density—a problem constraint to a variable ratio—induces underparametrization in fixed depth QAOA. Density-dependent performance has been reported in the literature, yet the circuit depth required to achieve fixed performance (henceforth called critical depth) remained unknown. Here, we propose a predictive model, based on a logistic saturation conjecture for critical depth scaling with respect to density. Focusing on random instances of MAX-2-SAT, we test our predictive model against simulated data with up to 15 qubits. We report the average critical depth, required to attain a success probability of 0.7, saturates at a value of 10 for densities beyond 4. We observe the predictive model to describe the simulated data within a confidence interval. Furthermore, based on the model, a linear trend for the critical depth with respect to problem size is recovered for the range of 5–15 qubits.- Open Access
- 26 July 2022
- Published by MDPI AG in Mathematics
- Vol. 10 (15) , 2601
Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation
The quantum approximate optimisation algorithm is a p layer, time variable split operator method executed on a quantum processor and driven to convergence by classical outer-loop optimisation. The classical co-processor varies individual application times of a problem/driver propagator sequence to prepare a state which approximately minimises the problem’s generator. Analytical solutions to choose optimal application times (called parameters or angles) have proven difficult to find, whereas outer-loop optimisation is resource intensive. Here we prove that the optimal quantum approximate optimisation algorithm parameters for layer reduce to one free variable and in the thermodynamic limit, we recover optimal angles. We moreover demonstrate that conditions for vanishing gradients of the overlap function share a similar form which leads to a linear relation between circuit parameters, independent of the number of qubits. Finally, we present a list of numerical effects, observed for particular system size and circuit depth, which are yet to be explained analytically.- 26 July 2022
- Published by MDPI AG in Mathematics
- Vol. 10 (15) , 2601
Open AccessProgress towards Analytically Optimal Angles in Quantum Approximate Optimisation
The quantum approximate optimisation algorithm is a p layer, time variable split operator method executed on a quantum processor and driven to convergence by classical outer-loop optimisation. The classical co-processor varies individual application times of a problem/driver propagator sequence to prepare a state which approximately minimises the problem’s generator. Analytical solutions to choose optimal application times (called parameters or angles) have proven difficult to find, whereas outer-loop optimisation is resource intensive. Here we prove that the optimal quantum approximate optimisation algorithm parameters for layer reduce to one free variable and in the thermodynamic limit, we recover optimal angles. We moreover demonstrate that conditions for vanishing gradients of the overlap function share a similar form which leads to a linear relation between circuit parameters, independent of the number of qubits. Finally, we present a list of numerical effects, observed for particular system size and circuit depth, which are yet to be explained analytically. - 15 September 2021
- Published by American Physical Society (APS) in Physical Review A
- Vol. 104 (3) , L030401
Training saturation in layerwise quantum approximate optimization
The quantum approximate optimization algorithm (QAOA) is the most studied gate-based variational quantum algorithm today. We train QAOA one layer at a time to maximize overlap with an qubit target state. Doing so we discovered that such training always saturates—called training saturation—at some depth , meaning that past a certain depth, overlap cannot be improved by adding subsequent layers. We formulate necessary conditions for saturation. Numerically, we find layerwise QAOA reaches its maximum overlap at depth for the problem of state preparation. The addition of coherent dephasing errors to training removes saturation, recovering robustness to layerwise training. This study sheds new light on the performance limitations and prospects of QAOA.- 15 September 2021
- Published by American Physical Society (APS) in Physical Review A
- Vol. 104 (3) , L030401
Training saturation in layerwise quantum approximate optimization
The quantum approximate optimization algorithm (QAOA) is the most studied gate-based variational quantum algorithm today. We train QAOA one layer at a time to maximize overlap with an qubit target state. Doing so we discovered that such training always saturates—called training saturation—at some depth , meaning that past a certain depth, overlap cannot be improved by adding subsequent layers. We formulate necessary conditions for saturation. Numerically, we find layerwise QAOA reaches its maximum overlap at depth for the problem of state preparation. The addition of coherent dephasing errors to training removes saturation, recovering robustness to layerwise training. This study sheds new light on the performance limitations and prospects of QAOA.- Open Access
- 30 August 2021
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 5, 532
Reachability Deficits in Quantum Approximate Optimization of Graph Problems
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.- 30 August 2021
- Published by Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften in Quantum
- Vol. 5, 532
Open AccessReachability Deficits in Quantum Approximate Optimization of Graph Problems
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits. - Open Access
Reachability Deficits in Quantum Approximate Optimization of Graph Problems
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
Open AccessReachability Deficits in Quantum Approximate Optimization of Graph Problems
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the \emph{density} of problem constraints versus problem variables acts as a performance indicator. Density is found to correlate strongly with approximation inefficiency for fixed depth QAOA applied to random graph minimization problem instances. Further, the required depth for accurate QAOA solution to graph problem instances scales critically with density. Motivated by Google's recent experimental realization of QAOA, we preform a reanalysis of the reported data reproduced in an ideal noiseless setting. We found that the reported capabilities of instances addressed experimentally by Google, approach a rapid fall-off region in approximation quality experienced beyond intermediate-density. Our findings offer new insight into performance analysis of contemporary quantum optimization algorithms and contradict recent speculation regarding low-depth QAOA performance benefits.
- 7 July 2021
- Published by American Physical Society (APS) in Physical Review A
- Vol. 104 (1) , L010401
Parameter concentrations in quantum approximate optimization
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. In QAOA, a quantum circuit is trained—by repeatedly adjusting circuit parameters—to solve a problem instance. Several recent findings have reported parameter concentration effects in QAOA and their presence has become one of folklore: while empirically observed, the concentrations have not been defined and analytical approaches remain scarce, focusing on limiting system sizes while neglecting parameter scaling as system size increases. We found that optimal QAOA circuit parameters concentrate as an inverse polynomial in the problem size, providing an optimistic result for improving circuit training. Our results are analytically demonstrated for QAOA at (corresponding to 2 and 4 tunable parameters, respectively). The technique is also applicable for higher depths wherein the concentration effect is cross verified numerically. Parameter concentrations allow for training on a fraction of qubits to assert that these parameters are nearly optimal on qubits, thereby reducing training time.- 7 July 2021
- Published by American Physical Society (APS) in Physical Review A
- Vol. 104 (1) , L010401
Parameter concentrations in quantum approximate optimization
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. In QAOA, a quantum circuit is trained—by repeatedly adjusting circuit parameters—to solve a problem instance. Several recent findings have reported parameter concentration effects in QAOA and their presence has become one of folklore: while empirically observed, the concentrations have not been defined and analytical approaches remain scarce, focusing on limiting system sizes while neglecting parameter scaling as system size increases. We found that optimal QAOA circuit parameters concentrate as an inverse polynomial in the problem size, providing an optimistic result for improving circuit training. Our results are analytically demonstrated for QAOA at (corresponding to 2 and 4 tunable parameters, respectively). The technique is also applicable for higher depths wherein the concentration effect is cross verified numerically. Parameter concentrations allow for training on a fraction of qubits to assert that these parameters are nearly optimal on qubits, thereby reducing training time.- Open Access
Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
While there are various approaches to benchmark physical processors, recent findings have focused on computational phase transitions. This is due to several factors. Importantly, the hardest instances appear to be well-concentrated in a narrow region, with a control parameter allowing uniform random distributions of problem instances with similar computational challenge. It has been established that one could observe a computational phase transition in a distribution produced from coherent Ising machine(s). In terms of quantum approximate optimisation, the ability for the quantum algorithm to function depends critically on the ratio of a problems constraint to variable ratio (called density). The critical density dependence on performance resulted in what was called, reachability deficits. In this perspective we recall the background needed to understand how to apply computational phase transitions in various bench-marking tasks and we survey several such contemporary findings.
Open AccessComputational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
While there are various approaches to benchmark physical processors, recent findings have focused on computational phase transitions. This is due to several factors. Importantly, the hardest instances appear to be well-concentrated in a narrow region, with a control parameter allowing uniform random distributions of problem instances with similar computational challenge. It has been established that one could observe a computational phase transition in a distribution produced from coherent Ising machine(s). In terms of quantum approximate optimisation, the ability for the quantum algorithm to function depends critically on the ratio of a problems constraint to variable ratio (called density). The critical density dependence on performance resulted in what was called, reachability deficits. In this perspective we recall the background needed to understand how to apply computational phase transitions in various bench-marking tasks and we survey several such contemporary findings.
- 5 March 2020
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 124 (9) , 090504
Reachability Deficits in Quantum Approximate Optimization
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm’s ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio—this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
- 5 March 2020
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 124 (9) , 090504
Reachability Deficits in Quantum Approximate Optimization
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm’s ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio—this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.
- Open Access
Reachability Deficits in Quantum Approximate Optimization
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithms ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio$-$this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such $reachability~deficits$ persist even in the absence of barren plateaus [McClean et al., 2018] and are outside of the recently reported level-1 QAOA limitations [Hastings 2019]. These findings are among the first to determine strong limitations on variational quantum approximate optimization.Open AccessReachability Deficits in Quantum Approximate Optimization
The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithms ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio$-$this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such $reachability~deficits$ persist even in the absence of barren plateaus [McClean et al., 2018] and are outside of the recently reported level-1 QAOA limitations [Hastings 2019]. These findings are among the first to determine strong limitations on variational quantum approximate optimization.