How can space and time arise from nothing? Lawrence Krauss said this on an Australian Q&A programme.
"...when you apply quantum mechanics to gravity, space itself can arise from nothing as can time..."
Can you elaborate on this please?  
It's hard to search for!
 A: Think of the uncertainty principle. According the the uncertainty principle, over a period of time energy fluctuates and combining this notion with relativity, this translates to virtual particles popping in and out of existence from the 'nothingness' of the vacuum. If we have a quantum theory of gravity (which we don't yet), space and time can behave like virtual particles and become quantum mechanical entities and hence pop in and out of existence due to the uncertainty principle. 
We still don't know how to combine general relativity with quantum mechanics. Such a stark incompatibility between the two arises because of the Uncertainty principle; in general relativity, perfectly flat space arises in the absence of a significant mass (such as the quantum vacuum) and thus the value of the gravitational field should be exactly zero. However, the Uncertainty principle needs only a mean value of zero and so the value of the gravitational field can fluctuate in a random 'foam'; therefore we get infinities (or ultraviolet divergences). Quantum gravity is currently nonrenormalisable 
A: You are probably expecting an answer about mutual particles and anti-particles spontaneously appearing in the quantum vacuum.  However, philosphically, 'nothing' has been described as "the purest indeterminate possibility of everything possible"[1], which is, in the ordo cognoscendi, prior to the quantum vacuum.


*

*ref: Critical Phenomenological Discussion of Some Traditional Theses about Being
As for the notion of everything accumulating from spontaneous manifestions in the quantum vacuum, I would suggest you watch Roger Penrose's lecture "Before the Big Bang?" on YouTube, or read up on it, eg[2].  His "smooth" state of the universe between Big Bangs is suggestive of the quantum vacuum, (though I expect not the same).  Penrose's theory proposes an alternative to one-time spontaneous manifestation, in that his model is cyclic, so whatever exists (whether jagged or smooth) may have always existed, and therefore has only truly come from 'nothing' in the philosophical sense.


*

*ref: Critical Phenomenological Discussion of Some Traditional Theses about Being

*Sir Roger Penrose: Alternate Theory of the Big Bang

"As the universe nears the end of its expansion, the remainder of its
  black holes will evaporate or gobble one another up, thus setting
  things back into a state of order. During this period, the universe
  would begin to revert back into a similar state it was in at the big
  bang, when the geometry of spacetime will become smooth again, which
  is in stark contrast to its current jagged form. According to
  Penroses' model, this will usher in the new aeon, AFTER  the universe
  is no longer able to expand any further. So it collapses back in on
  itself as a highly ordered system. One that that is ready to trigger
  the next "big bang.'"

A: The word "nothing" here is used somewhat loosely.  What Krauss means by nothing is no particles.  But, there is still the vacuum state of the quantum fields, which is something.  And those vacuum states can give rise to phenomena out of "nothing".
A: The point is that spacetime can be emergent, i.e., you don't put it in by hand from the start, but it sort of pops out at you along the way.
Sometimes the dynamical degrees of freedom (the variables of the theory, if you like) can be different depending on how you describe the system. The best known example is string theory, where you start with an ordinary conformal field theory in 2 dimensions (no gravity, not really space-time per se), and out pops a 10-dimensional theory of quantum gravity. Oh, and stare at it from another end, and it looks like a theory of infinite dimensional matrices (no space, just time).
The AdS/CFT duality is another, related example, where on one hand you have a field theory in 4 dimensions, but no gravity, and on the other hand you have a theory in 5 dimensions, plus gravity, and you're really just looking at two parts of the same elephant.
There is also loop quantum gravity, causal dynamical triangulations, etc., but these are not as well established nor as successful.
The relevant search terms are induced gravity, emergent gravity, emergent spacetime, etc.
A: This is not so much an answer as a comment and caution:  ex nihilo nihil fit (from nothing nothing is produced).
From Wikipedia:

It is important, however, to recognize what a physicist may mean by
  the word nothing. Some physicists, such as Lawrence Krauss, define
  nothing as an unstable quantum vacuum that contains no particles.
  This is incompatible with the philosophical definition of nothing,
  since it can be defined by certain properties such as space, and is
  governed by physical laws. Indeed, many philosophers criticize these
  physical explanations of how the universe arose from nothing, claiming
  that they merely beg the question.

A: Space and time, as ordinarily understood, came into being after the Big Bang and after the temperature of the universe decreased to the point that the particles (matter) created could not revert back to energy.  
When two "permanent" particles were created, space (distance between the particles) was created, and the relative motion between them, created time.   
A: Even going back to Newton, space and time are the consequences of measurement.
From the Principia's Scholium 

Relative time is a measure of duration by the means of motion; Relative space is a measure of the absolute spaces determined by the senses.

So they came from measurement. Not from nothing.
