Mechanical oscillators have been demonstrated with very high quality factors over a wide range of frequencies. These also couple to a wide variety of fields and forces, making them ideal as sensors. The realization of a mechanically-based quantum bit could therefore provide an important new platform for quantum computation and sensing. Here we show that by coupling one of the flexural modes of a suspended carbon nanotube to the charge states of a double quantum dot defined in the nanotube, it is possible to induce sufficient anharmonicity in the mechanical oscillator so that the coupled system can be used as a mechanical quantum bit. This can however only be achieved when the device enters the ultrastrong coupling regime. We discuss the conditions for the anharmonicity to appear, and we show that the Hamiltonian can be mapped onto an anharmonic oscillator, allowing us to work out the energy level structure and how decoherence from the quantum dot and the mechanical oscillator are inherited by the qubit. Remarkably, the dephasing due to the quantum dot is expected to be reduced by several orders of magnitude in the coupled system. We outline qubit control, readout protocols, the realization of a CNOT gate by coupling two qubits to microwave cavity, and finally how the qubit can be used as a static force quantum sensor.

19 pages, 11 figures. Final version published on Physical Review X. Replacement includes a new section on the CNOT gate