Quantum computation

A couple of days back, I received an interesting email from a rather curious mind.

The author of said email apparently found my contact details from one of the conference proceeding where I had submitted a paper.

Now, the author of the email posed rather curious questions, namely

…what exactly makes a quantum computer different from normal?…numerous articles point that quantum computer are superior because they can exist in two simultaneous states, but how does that exactly make a difference?…Lastly, every machine has its limits, so why is it being flaunted around as super machine?

Admittedly, given this was second email to me from a curious student so I was rather existed to answer it. Mind you, this person was also first one to continue conversations with follow up emails.

Anyways, while I did replied answers to all his questions, to the best of my abilities, it was later that I stumbled around this excellent article “What Quantum Computers Do Faster, with Caveats“. It is excellent articles that explains in short about the limitations of quantum computation. The author of this articles also uses Quantum Fourier Transform as example to explain the limitations.

One of the main idea about quantum world that I found hard to explain to him was that of superposition, something which he found surprisingly difficult to grasp; which may be attributed to his completely non-physics background.

When I had started to study about quantum information processing, I used to note down every interesting example or problem that would be capable of explaining a specific concept in a flash. Following is one of those noted example:

For example related to computer programming for understanding the superposition, one may look at a data structure called a linked list. Each data node in the list contains a pointer, to the next data node. The program traverses the list by jumping to the next data node indicated by the pointer. In a doubly-linked list, the data node contains two pointers, one for traversing to the top of the list, and another for traversing to the bottom of the list.

Another way of implementing a doubly-linked list is to use a single pointer space that contains the exclusive-or (XOR) or the two adjacent pointers. Figure below shows a link list node with pointer S that is the XOR of reference A (before) and reference B(after). To traverse the link list upward, the program XORs the current pointer (S) with the one it just left (B), and the result is the pointer of the next node (A). The same process works when traversing down the list. This superpositioning of node pointers is analogous to how the quantum states are maintained simultaneously in a quantum bit.

We can define those lists mathematically as follow:

 A = S \wedge B \uparrow


B = S \wedge A \downarrow


Earlier on, I also had bad habit of never noting down important points without due citation or source for the information. So credit for this example to original poster or author of blog post or paper, respectively. If anyone is aware of where this appears, kindly comment.

Lastly, there are two excellent articles on the Limits of Quantum Computers by Scott Aaronson here and here.

On the next Q+ Hangout

The next Q+ hangout is all set to run on 22nd April, 14:00 UTC+1. Surprisingly, the topic this time “On the Uncertainty of the Ordering of Nonlocal Wavefunction Collapse when Relativity is Considered”, which I had earlier read through and found to be highly interesting and no less entangled, no pun.

In the EPR experiment, if Alice makes a measurement on her particle then the state of Bob’s particle collapses to the result anti-correlated to Alice’s measurement. This process is said to be  happen instantaneously.

This ‘instantaneous’ gives rise to a paradox. For example, if in one reference frame Alice measures first then Bob’s state collapses. In a different inertial frame, an observer might say that Bob measured first leading to the collapse of Alice’s state. This leads to the identity paradox for who collapsed whose first!

This paper uses a type of clock device that functions on the laws of quantum-mechanics. This device in the experiment keeps the above paradox from occurring.

The bottom line being that in the experiment, Alice and Bob’s measurements cannot be made with infinite precision, rather they are constrained due to the energy-time uncertainty principle. Since energy and time are not relativistic invariant quantities, different observers in different reference frames must transform their uncertainty principles accordingly.

Concluding the paper rightfully claims the uncertainty principle in time always outruns the time difference induced by the change in reference frames. Neither Alice nor Bob will ever, with certainty, observe the two measurements swap temporal order. Furthermore, it can be said that  if a time measurement performed an entangled biphoton is simultaneous in one shared reference frame then it can be considered simultaneous to all measuring observers who do not share a reference frame.

On a personal note, it was only while going through the paper I thought about the time it takes for a EPR photon to collapse when measurement taken on its pair. People have already calculated it experimentally. This hangout already sounds like exciting, fingers crossed that I can attend it uninterrupted this time, have a couple of questions for the presenter.

Further Reading

On the Uncertainty of the Ordering of Nonlocal Wavefunction Collapse when Relativity is Considered arXiv:1310.4956 [quant-ph]

The Uncertainty Relation Between Energy and Time in Non-relativistic Quantum Mechanics DOI: 10.1007/978-3-642-74626-0_8

Experimental test of relativistic quantum state collapse with moving reference frames DOI: 10.1088/0305-4470/34/35/334

Apostille by MEA (Ministry of External Affairs), India [PART 2]

This is in continuation of my previous post Apostille by MEA (Ministry of External Affairs), India [PART 1].

This information is current as of April 2nd 2014 and applicable for educational documents ONLY.

The following is true for Maharashtra State Government. State attestation can be completed in one day, in official work hours.

State Attestation:

I.                   After completing the previous step, collect the following documents:

  • One Xerox copy of your passport, make sure that the Xerox has both the pages of your passport. The address page and the identification page. This Xerox copy must be self-attested. Be sure to also carry your passport.
  • All the original documents with due stamps from university and notary stamp.
  • One written application to Joint Secretory stating why you seek state-attestation.  Be sure to attach all relevant information in it for e.g. the name of the program and university which seeks apostille etc. The application must be signed by applicant.
  • Two passport size photos.
  • 1 blue pen and 1 black.
  • One nice book or perhaps portable video player to pass time (trust me it would be life saver).
  • Attestation is free of charge but be sure to carry change cash as you will need to pay for some Xerox.

II.               Travel to Mumbai. It is highly recommended that you travel as early as possible (on weekdays and non-national or state holidays only). 

  • The address one needs to travel first is:

Higher & Technical Education Department, Government of Maharashtra, Room No. 422, 4th floor,  Mantralaya, Mumbai – 400032. Tel No.: 022-22043018.

  • There are two ways you can travel there, by local bus, which runs every day during morning from every major bus stop or by local train. My city has bus daily directly till Mantralaya so I cannot provide accurate information about local trains, but from the enquiries I did with people around Mantralaya, local trains for Church gate were ideal option for reaching there.
  • Once you have reached there, from 9:30 the distribution of gate pass begins. First task is to secure a gate pass, fill up all the relevant information on it. Once filled up, queue for getting your pass authorized. You need to furnish original identification card to get your pass authorized. ID card can be: Driving License, PAN Card, and Passport.
  • Your gate pass would provide you the entry time as after 14:00. For now, keep the pass secured with you.
  • The reason to secure the gate pass earlier is due to the huge influx of people that gather for securing pass at later time.

III.            Around 13:20, line up for entry to Home department.

  • The Home Department of Maharashtra Government is situated in another building. The complete address is:

Section officer, Home Department, Government of Maharashtra, 9th floor, New Administrative Building, Opp. Mantralaya, Mumbai – 400032. Tel No. 022-22022688

  • This building in directly behind the one where you secured the gate pass. The other building does not require gate pass.
  • You need to note down purpose of visit with the security person. Additionally you need to furnish ID proof as well. Just write down 9th floor in place of department you wish to visit.
  • Once inside you can either take elevator or stairs to reach 9th floor. When I reached inside, there were queues (!) to use the elevator. I took up stairs rather than wasting time waiting for my turn.
  • On 9th floor the Home Department is exactly to the left side, if you arrived from staircase.
  • Go inside the first compartment of the Home Department.
  • Inside, the first table would provide you with first set of stamps and the other tables with signatures.
  • You will be asked for ID proof (if presenting the documents yourself, in case of proxy, a signed consent letter is required)

IV.             After completing with Home Department

  • Head back to the road where you sought the gate pass. Now head down the road, you will find yourself at a ‘T’ junction. Head left to find some Xerox shops.
  • Take two copies of all the original documents. Take Xerox of both sides.

V.                Head back to Mantralaya

  • Go to 4th floor of the Mantralaya building. On that floor ask anyone to point you towards Higher and Technical Education Department.
  • Inside, seek the lady (as of now) sitting at the desk which is infront of the cabin in the department.
  • Ask her to provide form for state attestation.
  • Fill the form in Black ink only. You will need to note down all the documents and its associated unique number on the form, which you seek attestation for. Also specify contact details of two persons in you locality to vouch for your behavior.
  • Paste you passport size photo to the application form.
  • Staple the written application and passport Xerox to the form.
  • Submit all the above along with Originals and Xerox of the same.
  • It will be checked and stamped in an hour or so.
  • For me it took 2 hours since the Joint Secretory was busy in meetings.

That’s all with state attestation. Final apostille procedure will be detailed in next post.


  • The toilets and wash rooms are 2 minutes distance from Mantralaya building (You cannot use the one available inside the building). It is near the bus stop.
  • There are some good places for having lunch or light snacks nearby. Be sure to ask the police force in case of any assistance in finding right place.
  • When you receive your documents back, be sure to double check if all the documents are stamped and signed. It happened with me that one document was unsigned.
  • You can use the free time in between taking gate pass and queuing for Home department by reading nice book or listening music etc.

Apostille by MEA (Ministry of External Affairs), India [PART 1]

I finally received my documents with apostille seal on them.  In this post, all the procedures and necessary steps in details along with some tips that might help people in getting their documents apostilled in timely and non-frustrated way, is listed.

All the information would be split into 2 parts. Second post would soon follow.

This information is current as of April 2nd 2014 and applicable for educational documents ONLY.


My documents originated from Maharashtra state, hence I needed state attestation prior to submitting documents for apostille. According to the stated information at MEA Official Site, one needs to get educational documents attested by Joint Secretory of Higher and Technical Education.

Unfortunately, the information listed on the MEA site is incomplete, as before the Joint Secretory can affix the documents, it must be stamped by the originating university’s registrar/controller of examination followed Notary by notarized person, ending with stamp from Home department of the state government. Thus the following steps apply:

I.              Get all the originals that you wish to aspotille, stamped from the relevant university (incase of higher education documents) or relevant examination board (incase of secondary or higher secondary education documents).

  • Be sure that the stamp is on original and the stamp states: ‘This documents has been verified and found OK’ OR ‘This documents has been checked and found authentic’ etc.
  • The stamp must also accompany signature of relevant examination authority like registrar/controller of examination etc.
  • In my case, the people at University refused to provide me such stamp claiming such stamp is not provided on originals or even on provisional certificate. First day was spend trying to convince them, but when all option failed, a direct application to Vice-Chancellor (VC) did wonders. The VC ordered the authorities to provide me with the stamps as he was pretty much aware of what exactly apostille is and its purpose! Overall, this process took 3 days.

II.            Get all the documents notarized by a notary person. You can search for notary person near you from this page. The notary must be of Rs. 25 stamp.

  •  It might happen that the Notary person would deny notarizing the original documents, as happened in my case. The solution to this problem would be to approach the Notary person with reference from someone who knows him and if it still doesn’t work then contact the Home Department of your state and have the person talk with them to clarify the issue.
  • This process should at-most take 1 hour, but due to reasons above it took me around  5 hours to convince and then for them to provide me with notary.

Next part would be about state attestation and final apostille procedures.

Intensive course: Quantum computing, logic and cognition

I have just submitted application for registration for Sixth International Summer School in Cognitive Sciences and Semantics. To be more specific, for the intensive course: Quantum computing, logic and cognition.

This school takes place at University of Latvia in Riga from 27 July to 29 July. And tuition fee is 100 Euro which will cover meals and coffee breaks.

For more information: http://www.lu.lv/isscss/

Life so far…

Its almost 3 months since my last entry but alas life has been giving way to many lemons as such I was busy making lemonades :P

To summarize, my mother was diagnosed with breast cancer in couple of days after my last entry. End of the last year and beginning of the new one was occupied with consulting medical peoples which immediately followed surgery and the recovery after that.

Meanwhile, as results for degree were yet to declared I could not apply for a program I had in mind :( Have applied for other programs after results and await the outcomes, which will start rolling out in a couple of weeks.

Additionally, attended two workshops, first being for Image processing and other Statistics for Experimental researcher.

The most frustrating, annoying and time consuming task during these months was getting Apostille certificates on all my documents. I will post up a separate entry detailing all the tasks about getting the process done in India.

That’s all for now. Hopefully blogging will be back not normal now.

Removing RSA keys by acoustic cryptanalysis



Image from: xkcd

The famous cryptographer Adi Shamir and his colleagues published a scientific paper titled “RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis

Many computers emit high frequency sound during operation, because of the vibrations in some electronic components (capacitors) caused due to microscopic variations in the voltage of the CPU during different workload on it. In theory, these sound vibrations can be analyzed in order to obtain information about the running application software, including cryptographic calculations. In 2004 year, Shamir and his colleagues have shown that different RSA keys cause different sound patterns, but back then it could not be understood how to extract individual bits keys. The main problem was that the sound equipment was unable to record sound with a high sampling frequency: 20 Khz only for conventional microphones and a few hundred kilohertz for ultrasonic microphones. This is many orders of magnitude low than several GHz, which is operated in modern computers.

Now they have demonstrated it with a software that extracts the full 4096-bit keys with GnuPG computers of various models after an hour of listening, if the computer all the time performs decryption. Conducted successful demonstration of such an attack using a smartphone, which lay 30 cm from the computer.


When using the directional microphone can attack from a distance of up to 4 metres.


If miniature hidden microphones are used, the maximum distance is about 1 meter. All equipment on the photos, in addition to microphones, can be hidden under a desk or in another discrete location.

At large scale, it seriously pose a threat and perhaps having organizational severs in fully shielded rooms would prevent it.

Photos from the paper.

The TrueCrypt Audit

Given the recent news about NSA’s ability to foil encryption soft wares, cryptographer Matthew Green and Kenneth White has started an initiative to examine the Truecrypt disk encryption tool.

Why does it matter?

Since NSA has been snooping in our data without us knowing, decryption of SSL connections and tampering with established standards to make them vulnerable, there needs to be an audit to verify that encryption softwares are truly as secure as they should be. For this very purpose there needs to be an extensive audit of softwares like Truecrypt which is used by many people, including me to a certain extent, for storing sensitive information.

How would the ‘audit’ work?

  • First step would be to resolve license status on the current (v. 7.1a) TrueCrypt source code (license v. 3.0 ) copyright & distribution, in order to create a verified, independent version control history repository (signed source and binary)
  • Perform and document repeatable, deterministic builds of TC 7.1a from source code for current major operating systems: Windows 7, Mac Mac OS X (Lion 10.7 and Mountain Lion 10.8), Ubuntu 12.04 LTS and 13.04, RedHat 6.4, CentOS 6.4, Debian 7.1, Fedora 19
  • Conduct a public cryptanalysis and security audit of version 7.1a

I wholly support this cause and hope everyone would help ensure we have trustworthy encryption available.


To contribute you can check the FundFill site, or IndieGoGo site. [Note: Both sites accept Credit cards; Fundfill accepts Bitcoins and IndieGoGo accepts Paypal and eChecks]

Contributions are not limited to monetary only but if you’re an information security professional/expert/hobbyist then you can help identify bugs in the software.

Official Site

Support the effort to audit TrueCrypt

Exact quantum query algorithms

Sankalp Ghatpande:

For the paper “Exact quantum query complexity of EXACT and THRESHOLD” by Andris Ambainis, Jānis Iraids & Juris Smotrovs; Maris Ozols, on his blog has posted an excellent analysis of this paper.

Originally posted on Mamuta memuāri:

Andris Ambainis, Jānis Iraids, and Juris Smotrovs recently have obtained some interesting quantum query algorithms [AIS13]. In this blog post I will explain my understanding of their result.

Throughout the post I will consider a specific type of quantum query algorithms which I will refer to as MCQ algorithms (the origin of this name will become clear shortly). They have the following two defining features:

  • they are exact (i.e., find answer with certainty)
  • they measure after each query

Quantum effects in an MCQ algorithm can take place only for a very short time — during the query. After the query the state is measured and becomes classical. Thus, answers obtained from two different queries do not interfere quantumly. This is very similar to deterministic classical algorithms that also find answer with certainty and whose state is deterministic after each query.

Basics of quantum query complexity

Our goal is…

View original 1,265 more words

meQuanics – The Quantum Computing Game

Researchers from National Institute of Informatics(NII) have published a Web applications to advance the study of the quantum computer in the form of a game ‘meQuanics‘; previously called as “Qubit – the game“. It is basically a puzzle game where the puzzles are represented as circuit of the quantum computer. Each puzzle in meQuanics represents a real quantum algorithm. Even users who do not possess any knowledge of quantum mechanics can contribute to optimizing quantum circuits by solving the puzzles in the game. The stages/levels are divided into different circuits including : Shor, Josza, Bell, Muller and more.

The goal in the game is operating a ship that is loaded with quantum computer. If user can reduce the size of the puzzle that shows a quantum circuit, the speed of the ship is improved.

meQuanics is a project initiated in the Quantum Information Science Theory group (QIST) led by Prof. Kae Nemoto at the National Institute of Informatics (NII) in Tokyo, Japan. Dr. Simon Devitt and Prof. Nemoto conceived the idea during their ongoing research into large-scale quantum architecture design.

Currently meQuanics is provided as a Web application called trial version for now, but will be further developed as a fully integrated crowd sourced game for iOS, Android, Windows, MacOS and Linux platforms.

Here are some screenshots :

EDIT: For those who are curious in Quantum Algorithms visit : The quantum zoo