- Utkarsh Azad, Center for Computational Natural Sciences and Bioinformatics (CCNSB) working under the supervision of Prof. Harjinder Singh presented a poster on Surface Code Design for Asymmetric Error Channels at a Workshop on Quantum Information Science and Engineering (QISE-2021) organized by the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-2021) on 18 December. The other authors of this research work are Aleksandra Lipińska, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków; Shilpa Mahato, Department of Physics, Indian Institute of Technology, Dhanbad; Rijul Sachdeva, Jülich Supercomputing Center, Forschungszentrum Jülich and RWTH Aachen University; Debasmita Bhoumik; Advanced Computing & Microelectronics Unit, Indian Statistical Institute, Kolkata; Ritajit Majumdar, Advanced Computing & Microelectronics Unit, Indian Statistical Institute, Kolkata. Research work as explained by the authors:
Surface codes are quantum error correcting codes normally defined on 2D arrays of qubits. In this paper, we introduce a surface code design based on the fact that the severity of bit-flip and phase-flip errors in the physical quantum systems is asymmetric. For our proposed surface code design for asymmetric error channels, we resent pseudo-threshold and threshold values in the presence of various degrees of asymmetry of Pauli X, Y, and Z errors in a depolarization channel. We show that, compared to symmetric surface codes, our asymmetric surface codes can provide almost double the pseudo-threshold rates while requiring less than half the number of physical qubits in the presence of increasing asymmetry in the error channel. We also demonstrate that as the asymmetry of the surface code increases, the advantage in the pseudo-threshold rates begins to saturate for any degree of asymmetry in the channel.
Link to the poster: https://drive.google.com/file/d/1oOFy22neIIRwFVP-3mSZ9iDOV3lLpGb8/view?usp=sharing
- Dr. Suryajith Chillara, Center for Security, Theory and Algorithmic Research (CSTAR) presented a paper on Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four at 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Research work as explained by Dr. Suryajit Chillara:
Recently, Forbes, Kumar and Saptharishi [CCC, 2016] proved that there exists an explicit $d^{O(1)}$-variate and degree $d$ polynomial $P_{d} \in VNP$ such that if any depth four circuit $C$ of bounded formal degree $d$ which computes a polynomial of bounded individual degree $O(1)$, that is functionally equivalent to $P_d$, then $C$ must have size $2^{\Omega(\sqrt{d}\log{d})}$.
The motivation for their work comes from Boolean Circuit Complexity. Based on a characterization for $ACC^0$ circuits by Yao [FOCS, 1985] and Beigel and Tarui [CC, 1994], Forbes, Kumar and Saptharishi [CCC, 2016] observed that functions in $ACC^0$ can also be computed by algebraic $\Sigma\mathord{\wedge}\Sigma\Pi$ circuits (i.e., circuits of the form — sums of powers of polynomials) of $2^{\log^{O(1)}n}$ size. Thus they argued that a $2^{\omega(\log^{O(1)}{n})}$ *functional* lower bound for an explicit polynomial $Q$ against $\Sigma\mathord{\wedge}\Sigma\Pi$ circuits would imply a lower bound for the *corresponding Boolean function* of $Q$ against non-uniform $ACC^0$. In their work, they ask if their lower bound be extended to $\Sigma\mathord{\wedge}\Sigma\Pi$ circuits.
In this paper, for large integers $n$ and $d$ such that $\Omega(\log^2{n})\leq d\leq n^{0.01}$, we show that any $\Sigma\mathord{\wedge}\Sigma\Pi$ circuit of bounded individual degree at most $O(\frac{d}{k^2})$ that functionally computes Iterated Matrix Multiplication polynomial $IMM_{n,d}$ ($\in VP$) over ${\{0,1\}}^{n^2d}$ must have size $n^{\Omega(k)}$. Since Iterated Matrix Multiplication $IMM_{n,d}$ over $\{0,1\}^{n^2d}$ is functionally in $GapL$, improvement of the afore mentioned lower bound to hold for quasipolynomially large values of individual degree would imply a fine-grained separation of $ACC^0$ from $GapL$.
For the sake of completeness, we also show a syntactic size lower bound against any $\Sigma\mathord{\wedge}\Sigma\Pi$ circuit computing $IMM_{n,d}$ (for the same regime of $d$) which is tight over large fields. Like Forbes, Kumar and Saptharishi [CCC, 2016], we too prove lower bounds against circuits of bounded formal degree which functionally compute $IMM_{n,d}$, for a slightly larger range of individual degree.
Link to the conference proceeding: https://drops.dagstuhl.de/opus/frontdoor.php?source_opus=15525
Link to the online video of the talk: https://www.youtube.com/watch?v=DPz5YINghLw
QISE-2021 was intended to evolve into a regular yearly event providing a platform to a diverse audience for learning about the recent developments in areas related to quantum science in general and quantum computing in particular.
The first edition of QISE-2021, was to give an opportunity to provide a robust exposure to students, researchers and industry practitioners to the recent developments in quantum computation, from the point of view of computer science, physics, and engineering. Apart from this QISE-2021 also wanted to familiarize the participants, especially the students, to recent quantum computing and simulation tools, e.g., with the view to introducing them to quantum machine learning.
FSTTCS 2021 is the 41st conference on Foundations of Software Technology and Theoretical Computer Science. It was organised by IARCS, the Indian Association for Research in Computing Science, in association with ACM India. It is a forum for presenting original results in foundational aspects of Computer Science and Software Technology.
Due to the Covid situation in India and the rest of the world, and to rule out uncertainty for authors and the local organizers, FSTTCS 2021 was be held virtually.
Link to the conference: https://www.fsttcs.org.in/2021/
Link to the workshop: https://acm-goa.github.io/QISE/