Igor Zacharov

Dr. Igor Zacharov

orcid

Research Focus & Metrics

Academic Career Length

9Years (2018-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
30 August 2021 in Quantum
Verified
Journal Article
Open access
PDF file
VAV. Akshay
V. Akshay
HPH. Philathong
H. Philathong
IZIgor Zacharov
Igor Zacharov
Jacob D. BiamonteJacob D. Biamonte
Jacob D. Biamonte
The quantum approximate optimization algorithm (QAOA) has become a cornerstone of contemporary quantum applications development. Here we show that the 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.

29 May 2024 in Physical Review A
Verified
Journal Article
Closed access
PDF file
BABoris Arseniev
Boris Arseniev
DGDmitry Guskov
Dmitry Guskov
RSRichik Sengupta
Richik Sengupta
JBJacob Biamonte
Jacob Biamonte
IZIgor Zacharov
Igor Zacharov
The construction of quantum circuits to simulate Hamiltonian evolution is central to many quantum algorithms. State-of-the-art circuits are based on oracles whose implementation is often omitted, and the complexity of the algorithm is estimated by counting oracle queries. However, in practical applications, an oracle implementation contributes a large constant factor to the overall complexity of the algorithm. The key finding of this work is the efficient procedure for representation of a tridiagonal matrix in the Pauli basis, which allows one to construct a Hamiltonian evolution circuit without the use of oracles. The procedure represents a general tridiagonal matrix 2n×2n by systematically determining all Pauli strings present in the decomposition, dividing them into commuting subsets. The efficiency is in the number of commuting subsets O(n). The method is demonstrated using the one-dimensional wave equation, verifying numerically that the gate complexity as a function of the number of qubits is lower than the oracle-based approach for n<15 and requires half the number of qubits. This method is applicable to other Hamiltonians based on the tridiagonal matrices.

1 December 2023 in Journal of Physics: Complexity
Verified
Journal Article
Open access
PDF file
HPHariphan Philathong
Hariphan Philathong
VAVishwanathan Akshay
Vishwanathan Akshay
IZIgor Zacharov
Igor Zacharov
Jacob D. BiamonteJacob D. Biamonte
Jacob D. Biamonte
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.

28 April 2025 in Physical Review A
Verified
Journal Article
Closed access
BABoris Arseniev
Boris Arseniev
DGDmitry Guskov
Dmitry Guskov
RSRichik Sengupta
Richik Sengupta
IZIgor Zacharov
Igor Zacharov

1 January 2018
Verified
Conference Paper
Closed access
STSkolkovo Institute of Science and Technology
Skolkovo Institute of Science and Technology
IZIgor Zacharov
Igor Zacharov
OPOleg Anatolievich Panarin
Oleg Anatolievich Panarin

27 August 2021 in arXiv
Verified
Preprint
Open access
PDF file
VAV. Akshay
V. Akshay
HPH. Philathong
H. Philathong
IZIgor Zacharov
Igor Zacharov
JBJ. Biamonte
J. Biamonte
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.