Quantum Algorithms
Quantum Algorithms
The Theory Group at CQuERE works on quantum algorithms, primarily with a focus on many-body systems. My focus is rather from the computer science perspective to quantum algorithms. For example, we have been working on finding out the limits of quantum computers. This is important so that we know how far-reaching the power of quantum computers is. We have been working on finding an efficient quantum polynomial time algorithm for the SUBSET-SUM problem, which is to find out whether there exists a subset of a given set of integers that sums to zero. We have also found a quantum polynomial time algorithm for the problem of evaluating a complete binary NAND tree. Besides, we have also been working on an efficient quantum algorithm for the quantum state distinguishability problem, which is to find out whether two given arbitrary quantum states are the same or not. A thrust of our center is also translational research, towards which we have been working on finding an efficient quantum algorithm for the traveling salesman problem (TSP), which is to find out the shortest route that a salesman has to travel within a network of cities, so that he can cover all the cities without visiting a city more than once before returning to the starting city.
Existing machine learning models, classical or quantum, can be highly accurate, but can still go wrong on an unseen test data, no matter how well-trained or regularized. This is usually not a problem for most applications. However, there are situations when even the slightest of error in decision-making may not be tolerable. An example is a face recognition system, used as a security feature for access to highly classified information. Another example is that of a self-driving car, which can still kill a person, even if that chance is less than say 0.01%. It is important for such applications that the model be self-aware in some sense, so that it can stop itself from taking a wrong decision, that can be fatal. We are working on a novel machine learning model, that mimics quantum mechanical evolution, so that it can be made self-aware of when it can go wrong, so that it may or may not know the alternative correct course of action to take, but it can at least stop itself from taking the wrong decision. By being self-aware, we do not imply at all that the model would become conscious like humans. The model would just be imparted with an ability, based on quantum mechanics, to identify when it can go wrong on an unseen test data and what it should do in that case.
We explore the possibility of exploiting noise, rather than avoiding it, to improve and/or assist in quantum computation. Currently, the biggest problem with quantum computers is noise. It is increasingly becoming impractical to be able to keep scaling up quantum computers, because noise cannot be fundamentally reduced beyond a point through engineering advances alone. To this end, we would explore if and how current noisy intermediate-scale quantum (NISQ) hardware can be used judiciously, to do as good as, or even better than, what is known to be possible on future fault-tolerant quantum devices. Some existing literature already suggest that various quantum tasks can be done better with noise than without noise in some situations. This is because mixed entangled states can be doubly more non-classical than pure entangled states, and some non-unital noise, like amplitude damping, can introduce, rather than destroy, quantum correlations in quantum systems, as opposed to unital noise, like dephasing, that usually destroy useful quantum correlations in them.
Quantum State Tomography is the problem of estimating a given unknown arbitrary quantum state. It is a central problem in quantum information, and considerable efforts have been put to find out efficient ways of performing quantum state tomography. Because of the measurement problem and no-cloning theorem of quantum mechanics, the entire process of creating the given unknown state has to be repeated as many times as are the number of copies of the state required. This makes the estimation process very inefficient and impractical. We, therefore, have been working on an efficient quantum state tomography algorithm, requiring only a single copy of the given unknown arbitrary quantum state. Our technique also does not require any information about the evolution dynamics of the quantum state to estimate. Moreover, the original quantum state being estimated does not get destroyed, since we do not perform any measurement on the original state, and it can be easily restored for any further quantum information processing. It may sound as if this would violate the no-cloning theorem, but that is not true, since our protocol will work for small but non-zero error. There are other problems in quantum information, that is not just limited to quantum computation, that can be bottlenecks for efficient quantum information processing. For example, it is often crucial to be able to efficiently create a given quantum state that serves as an input to a quantum algorithm. Any quantum speedup that the quantum algorithm itself provides with can be nullified, if the desired initial quantum state is not easy/efficient enough to prepare. We have thus been exploring the task of efficiently creating an arbitrary quantum state from given classical data to address this bottleneck.
We explore the possibility of exploiting both spatial and temporal correlations in quantum computing and information. Extensive efforts over several decades have been put in to study spatial quantum correlations, which are now quite well understood as a consequence. Temporal correlations are now of significant interest since recently, whereby they have been shown to provide with advantage in the context of quantum information processing. Time is, however, not as well-defined in quantum theory and so understanding the behavior of quantum systems along the time dimension is very different from, but equally important as, that of quantum systems in space. A more holistic study of quantum systems must include both spatial and temporal correlations, defined uniformly on a common setting such as using a pseudo-density matrix formalism. It is of a foundational relevance to see the relative behavior of quantum systems in space with that in time, e.g. what is the interplay between quantum correlations in space with those in time, exhibited by a quantum system. Such insights are expected to provide us with comprehensive utilization of spatio-temporal correlations in quantum information.
Einstein always insisted that quantum mechanics cannot be the most fundamental theory of nature, and must arise as a special case of a more fundamental theory. It turns out, as I show in my work, that it is Einstein's own theory of general relativity, that is at the foundations of quantum mechanics. In other words, the science of small - quantum mechanics - has origins in the science of big - general relativity. We derived Heisenberg's uncertainty principle and Schrodinger equation from Newtonian gravity, that is the small curvature limit of the Schwarzschild metric from general relativity. We infer that quantum mechanics arises from ignoring the tiny spacetime (Riemannian) curvatures of Newtonian gravity for masses below the Planck mass. We show that tinier are these (external) curvatures that are ignored, larger would be the observable quantum effects. By contrast, masses above Planck mass cannot exhibit observable quantum behavior, unless it is possible for such masses to have velocities larger than the speed of light in vacuum. Ignoring the curvatures manifests as projecting them onto flat spacetime, so that quantum mechanics appears to exhibit paradoxical non-locality, although local realism is not violated in the actual curved spacetime. This is also why Newtonian gravity appears to have infinite speed, although when viewed as the static weak field limit of general relativity, it also propagates at the speed of light. We find that the quantum wavefunction coincides with the gravitational mass distribution of the particle, and its probability wave is nothing but a gravitational wave, that allows for the spreading of the wavefunction of the quantum particle.
Schrodinger famously said that Life is Information. However, there has to be more than information that must constitute life. In other words, it is important to understand what is to life that allows for the kind of information that gives rise to attributes of life. It is still a big mystery as to how inanimate matter becomes "living" at what point, as we zoom out of the microscopic quantum realm of atoms and molecules, while other forms of macroscopic matter do not admit life. It appears that life should not be possible without consciousness, that, in turn, must have a quantum origin. We anticipate that a key role in consciousness is played by the behavior and impact of noise in quantum systems, else it should not be possible for our brains to perform computations with a mere 20 Watts, that otherwise take a computer 20 Mega Watts. This is why our study of noise in quantum computation is expected to somewhat unlock the mystery of consciousness. This, in turn, should allow for "life", the equation for which should be some solution to Einstein's field equation from general relativity, if, as I claim, it is indeed general relativity that gives rise to quantum mechanics in flat spacetime below Planck mass.